← 返回题目列表

Codeforces · 771/E

E. 熊和矩形条

中文机器翻译题面 查看原题

Limak 有一个由 2 行 n 列组成的网格。第 i 行中的第 j 个单元格包含一个整数 ti, j,可以是正数、负数或零。

当且仅当单元格中的数字总和等于 0 时,非空单元格矩形才被称为良好。

Limak 想选择一些漂亮的矩形并将它们作为礼物送给他的朋友。任何两个选定的矩形不应共享一个单元格。 Limak 最多可以选择多少个漂亮的矩形?

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 300 000) — 网格中的列数。

接下来的两行包含网格中的数字。这两行中的第 i 行包含 n 个整数 ti, 1, ti, 2, ..., ti, n (- 109 ≤ ti, j ≤ 109)。

输出

打印一个整数,表示单元不相交的漂亮矩形的最大可能数量。

示例

输入 #1

6
70 70 70 70 70 -15
90 -60 -30 30 -30 15

输出 #1

3

输入 #2

4
0 -1 0 0
0 0 1 0

输出 #2

6

输入 #3

3
1000000000 999999999 -1000000000
999999999 -1000000000 -999999998

输出 #3

1

注意

在第一个示例中,有四个漂亮的矩形:

Limak 无法选择所有这些,因为它们不是不相交的。他应该选取三个漂亮的矩形:那些在图纸上标记为蓝色框的矩形。

在第二个示例中,最好选择六个漂亮的矩形,每个矩形由一个数字为 0 的单元格组成。

在第三个示例中,唯一的好矩形是整个网格 - 所有数字的总和为 0。显然,Limak 最多可以选择一个好矩形,因此答案为 1。