{"problem":{"name":"B. Intercepted Message","description":{"content":"Hacker Zhorik wants to decipher two secret messages he intercepted yesterday. Yeah message is a sequence of encrypted blocks, each of them consists of several bytes of information. Zhorik knows that ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF950B"},"statements":[{"statement_type":"Markdown","content":"Hacker Zhorik wants to decipher two secret messages he intercepted yesterday. Yeah message is a sequence of encrypted blocks, each of them consists of several bytes of information.\n\nZhorik knows that each of the messages is an archive containing one or more files. Zhorik knows how each of these archives was transferred through the network: if an archive consists of _k_ files of sizes _l_1, _l_2, ..., _l__k_ bytes, then the _i_\\-th file is split to one or more blocks _b__i_, 1, _b__i_, 2, ..., _b__i_, _m__i_ (here the total length of the blocks _b__i_, 1 + _b__i_, 2 + ... + _b__i_, _m__i_ is equal to the length of the file _l__i_), and after that all blocks are transferred through the network, maintaining the order of files in the archive.\n\nZhorik thinks that the two messages contain the same archive, because their total lengths are equal. However, each file can be split in blocks in different ways in the two messages.\n\nYou are given the lengths of blocks in each of the two messages. Help Zhorik to determine what is the maximum number of files could be in the archive, if the Zhorik's assumption is correct.\n\n## Input\n\nThe first line contains two integers _n_, _m_ (1 ≤ _n_, _m_ ≤ 105) — the number of blocks in the first and in the second messages.\n\nThe second line contains _n_ integers _x_1, _x_2, ..., _x__n_ (1 ≤ _x__i_ ≤ 106) — the length of the blocks that form the first message.\n\nThe third line contains _m_ integers _y_1, _y_2, ..., _y__m_ (1 ≤ _y__i_ ≤ 106) — the length of the blocks that form the second message.\n\nIt is guaranteed that _x_1 + ... + _x__n_ = _y_1 + ... + _y__m_. **Also, it is guaranteed that _x_1 + ... + _x__n_ ≤ 106.**\n\n## Output\n\nPrint the maximum number of files the intercepted array could consist of.\n\n[samples]\n\n## Note\n\nIn the first example the maximum number of files in the archive is 3. For example, it is possible that in the archive are three files of sizes 2 + 5 = 7, 15 = 3 + 1 + 11 = 8 + 2 + 4 + 1 and 4 + 4 = 8.\n\nIn the second example it is possible that the archive contains two files of sizes 1 and 110 = 10 + 100 = 100 + 10. Note that the order of files is kept while transferring archives through the network, so we can't say that there are three files of sizes 1, 10 and 100.\n\nIn the third example the only possibility is that the archive contains a single file of size 4.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"黑客佐里克想破译他昨天截获的两条秘密消息。每条消息是由若干加密块组成的序列，每个块包含若干字节的信息。\n\n佐里克知道，每条消息都是一个归档文件，包含一个或多个文件。佐里克了解这些归档文件通过网络传输的方式：如果一个归档文件包含 #cf_span[k] 个文件，其大小分别为 #cf_span[l1, l2, ..., lk] 字节，那么第 #cf_span[i] 个文件会被分割为一个或多个块 #cf_span[bi, 1, bi, 2, ..., bi, mi]（这些块的总长度 #cf_span[bi, 1 + bi, 2 + ... + bi, mi] 等于文件的长度 #cf_span[li]），然后所有块按照归档文件中文件的顺序传输。\n\n佐里克认为这两条消息包含相同的归档文件，因为它们的总长度相等。然而，每个文件在两条消息中可能被分割成不同的块。\n\n现在给你两条消息中每个块的长度。请帮助佐里克确定，如果他的假设正确，该归档文件最多可能包含多少个文件。\n\n第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 105]) —— 分别表示第一条和第二条消息中的块数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] (#cf_span[1 ≤ xi ≤ 106]) —— 表示第一条消息中各块的长度。\n\n第三行包含 #cf_span[m] 个整数 #cf_span[y1, y2, ..., ym] (#cf_span[1 ≤ yi ≤ 106]) —— 表示第二条消息中各块的长度。\n\n保证 #cf_span[x1 + ... + xn = y1 + ... + ym]。*同时保证 #cf_span[x1 + ... + xn ≤ 106]。*\n\n请输出该归档文件可能包含的最大文件数。\n\n在第一个例子中，归档文件最多可包含 3 个文件。例如，归档文件可能包含三个文件，其大小分别为 #cf_span[2 + 5 = 7]、#cf_span[15 = 3 + 1 + 11 = 8 + 2 + 4 + 1] 和 #cf_span[4 + 4 = 8]。\n\n在第二个例子中，归档文件可能包含两个文件，其大小分别为 #cf_span[1] 和 #cf_span[110 = 10 + 100 = 100 + 10]。注意，文件在传输过程中保持原有顺序，因此我们不能说存在三个大小分别为 #cf_span[1]、#cf_span[10] 和 #cf_span[100] 的文件。\n\n在第三个例子中，唯一可能是归档文件包含一个大小为 #cf_span[4] 的文件。\n\n## Input\n\n第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 105]) —— 分别表示第一条和第二条消息中的块数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] (#cf_span[1 ≤ xi ≤ 106]) —— 表示第一条消息中各块的长度。\n\n第三行包含 #cf_span[m] 个整数 #cf_span[y1, y2, ..., ym] (#cf_span[1 ≤ yi ≤ 106]) —— 表示第二条消息中各块的长度。\n\n保证 #cf_span[x1 + ... + xn = y1 + ... + ym]。*同时保证 #cf_span[x1 + ... + xn ≤ 106]。*\n\n## Output\n\n请输出该归档文件可能包含的最大文件数。\n\n[samples]\n\n## Note\n\n在第一个例子中，归档文件最多可包含 3 个文件。例如，归档文件可能包含三个文件，其大小分别为 #cf_span[2 + 5 = 7]、#cf_span[15 = 3 + 1 + 11 = 8 + 2 + 4 + 1] 和 #cf_span[4 + 4 = 8]。\n\n在第二个例子中，归档文件可能包含两个文件，其大小分别为 #cf_span[1] 和 #cf_span[110 = 10 + 100 = 100 + 10]。注意，文件在传输过程中保持原有顺序，因此我们不能说存在三个大小分别为 #cf_span[1]、#cf_span[10] 和 #cf_span[100] 的文件。\n\n在第三个例子中，唯一可能是归档文件包含一个大小为 #cf_span[4] 的文件。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ X = (x_1, x_2, \\dots, x_n) $ and $ Y = (y_1, y_2, \\dots, y_m) $ be two sequences of positive integers representing block lengths in the two messages.  \nLet $ S = \\sum_{i=1}^n x_i = \\sum_{j=1}^m y_j $ be the total size of the archive.\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 10^5 $  \n2. $ 1 \\leq x_i, y_j \\leq 10^6 $  \n3. $ \\sum_{i=1}^n x_i = \\sum_{j=1}^m y_j \\leq 10^6 $\n\n**Objective**  \nFind the maximum number $ k $ such that there exist partitions:  \n- $ X $ into $ k $ contiguous non-empty subsequences with sums $ l_1, l_2, \\dots, l_k $,  \n- $ Y $ into $ k $ contiguous non-empty subsequences with sums $ l_1, l_2, \\dots, l_k $,  \nin the same order.  \n\nThat is, find the maximum $ k $ for which there exists a sequence of partial sums:  \n$$\n0 = p_0 < p_1 < \\dots < p_k = n, \\quad 0 = q_0 < q_1 < \\dots < q_k = m\n$$  \nsuch that for all $ i \\in \\{1, \\dots, k\\} $:  \n$$\n\\sum_{j=p_{i-1}+1}^{p_i} x_j = \\sum_{j=q_{i-1}+1}^{q_i} y_j\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF950B","tags":["greedy","implementation"],"sample_group":[["7 6\n2 5 3 1 11 4 4\n7 8 2 4 1 8","3"],["3 3\n1 10 100\n1 100 10","2"],["1 4\n4\n1 1 1 1","1"]],"created_at":"2026-03-03 11:00:39"}}