{"code":"dplcs11","name":"Dãy con chung zigzag dài nhất","description":"Cho dãy $A$ gồm $N$ phần tử gồm các số nguyên dương $A_1, A_2, ..., A_N$ và dãy $B$ gồm $M$ phần tử gồm các số nguyên dương $B_1, B_2, ..., B_M$. Dãy $C$ được gọi là dãy con chung zigzag độ dài $K$ của $A, B$ nếu tồn tại hai dãy chỉ số như sau:\r\n+ $1 \\leq i_1 < i_2 < ... < i_K \\leq N$.\r\n+ $1 \\leq j_1 < j_2 < ... < j_K \\leq M$.\r\n\r\nSao cho $C_p = A_{i_p} = B_{j_p}$ và thoả mãn một trong hai điều kiện sau:\r\n+ $C_1 > C_2 < C_3 > ...$\r\n+ $C_1 < C_2 > C_3 < ...$\r\n\r\n**Yêu cầu**: Tìm dãy $C$ là dãy con chung zigzag của $A, B$ sao cho độ dài $K$ lớn nhất có thể.\r\n\r\n#### Input\r\n- Gồm ba dòng:\r\n+ Dòng thứ nhất chứa hai số nguyên dương $N, M$.\r\n+ Dòng thứ hai gồm $N$ số nguyên dương $A_1, A_2, ..., A_N$ $(A_i \\leq 10^6)$.\r\n+ Dòng thứ ba gồm $M$ số nguyên dương $B_1, B_2, ..., B_M$ $(B_i \\leq 10^6)$.\r\n\r\n#### Output\r\n- Gồm hai dòng:\r\n+ Dòng thứ nhất in ra số $K$ là độ dài dãy con chung $C$ dài nhất tìm được.\r\n+ Dòng thứ hai in ra $K$ số nguyên dương $C_1, C_2, ..., C_K$. Nếu có nhiều dãy $C$ thoả mãn, in ra một dãy bất kì.\r\n#### Scoring\r\n+ Subtask $1$ ($30\\%$ số điểm): $N, M \\leq 10^2$.\r\n+ Subtask $2$ ($30\\%$ số điểm): $N, M \\leq 10^3$.\r\n+ Subtask $3$ ($40\\%$ số điểm): $N, M \\leq 5.10^3$.\r\n+ Nếu in ra đúng số $K$ thì sẽ được $50\\%$ số điểm của test. Nếu in ra thêm được dãy $C_1, C_2, ..., C_K$ mà đúng sẽ được thêm $50$% số điểm của test.\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        6 8\r\n        4 3 6 5 8 7\r\n        2 4 1 6 5 1 8 7 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        5\r\n        4 6 5 8 7\r\n        ```","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}