E. Bear and Rectangle Strips

Codeforces

IDCF771E

Time3000ms

Memory256MB

Difficulty—

dpgreedy

English · Original

Chinese · Translation

Formal · Original

Limak has a grid that consists of 2 rows and _n_ columns. The _j_\-th cell in the _i_\-th row contains an integer _t__i_, _j_ which can be positive, negative or zero. A non-empty rectangle of cells is called _nice_ if and only if the sum of numbers in its cells is equal to 0. Limak wants to choose some nice rectangles and give them to his friends, as gifts. No two chosen rectangles should share a cell. What is the maximum possible number of nice rectangles Limak can choose? ## Input The first line of the input contains an integer _n_ (1 ≤ _n_ ≤ 300 000) — the number of columns in the grid. The next two lines contain numbers in the grid. The _i_\-th of those two lines contains _n_ integers _t__i_, 1, _t__i_, 2, ..., _t__i_, _n_ ( - 109 ≤ _t__i_, _j_ ≤ 109). ## Output Print one integer, denoting the maximum possible number of cell-disjoint nice rectangles. [samples] ## Note In the first sample, there are four nice rectangles: <center>![image](https://espresso.codeforces.com/590b3d4bdef7c3b8fae0715eceb1f89f78d849d8.png)</center>Limak can't choose all of them because they are not disjoint. He should take three nice rectangles: those denoted as blue frames on the drawings. In the second sample, it's optimal to choose six nice rectangles, each consisting of one cell with a number 0. In the third sample, the only nice rectangle is the whole grid — the sum of all numbers is 0. Clearly, Limak can choose at most one nice rectangle, so the answer is 1.

Limak 有一个由 #cf_span[2] 行和 #cf_span[n] 列组成的网格。第 #cf_span[i] 行第 #cf_span[j] 列的单元格包含一个整数 #cf_span[ti, j]，它可以是正数、负数或零。一个非空的矩形区域被称为 _nice_，当且仅当其中所有单元格的数字之和等于 #cf_span[0]。 Limak 想要选择一些 nice 矩形并把它们作为礼物送给朋友。所选的任意两个矩形不能共享任何单元格。求 Limak 最多能选择多少个 nice 矩形？输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300 000]) —— 网格的列数。接下来的两行包含网格中的数字。这两行中的第 #cf_span[i] 行包含 #cf_span[n] 个整数 #cf_span[ti, 1, ti, 2, ..., ti, n] (#cf_span[ - 109 ≤ ti, j ≤ 109])。请输出一个整数，表示最多能选择的互不重叠的 nice 矩形数量。在第一个样例中，有四个 nice 矩形： Limak 不能选择全部四个，因为它们不是互不重叠的。他应该选择三个 nice 矩形：即图中用蓝色框标出的那些。在第二个样例中，最优方案是选择六个 nice 矩形，每个由一个值为 #cf_span[0] 的单元格组成。在第三个样例中，唯一的 nice 矩形是整个网格——所有数字的和为 #cf_span[0]。显然，Limak 最多只能选择一个 nice 矩形，因此答案是 #cf_span[1]。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300 000]) —— 网格的列数。接下来的两行包含网格中的数字。这两行中的第 #cf_span[i] 行包含 #cf_span[n] 个整数 #cf_span[ti, 1, ti, 2, ..., ti, n] (#cf_span[ - 109 ≤ ti, j ≤ 109])。 ## Output 请输出一个整数，表示最多能选择的互不重叠的 nice 矩形数量。 [samples] ## Note 在第一个样例中，有四个 nice 矩形： Limak 不能选择全部四个，因为它们不是互不重叠的。他应该选择三个 nice 矩形：即图中用蓝色框标出的那些。在第二个样例中，最优方案是选择六个 nice 矩形，每个由一个值为 #cf_span[0] 的单元格组成。在第三个样例中，唯一的 nice 矩形是整个网格——所有数字的和为 #cf_span[0]。显然，Limak 最多只能选择一个 nice 矩形，因此答案是 #cf_span[1]。

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 300{,}000 $, be the number of columns. Let $ T = (t_{i,j}) \in \mathbb{Z}^{2 \times n} $ be a $ 2 \times n $ grid of integers. A *nice rectangle* is a non-empty axis-aligned subrectangle of $ T $ such that the sum of its elements is $ 0 $. **Constraints** - $ -10^9 \leq t_{i,j} \leq 10^9 $ for all $ i \in \{1,2\} $, $ j \in \{1,\dots,n\} $. - Chosen rectangles must be pairwise cell-disjoint. **Objective** Maximize the number of cell-disjoint nice rectangles.

Samples

Input #1

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

Output #1

Input #2

4
0 -1 0 0
0 0 1 0

Output #2

Input #3

3
1000000000 999999999 -1000000000
999999999 -1000000000 -999999998

Output #3

API Response (JSON)

{
  "problem": {
    "name": "E. Bear and Rectangle Strips",
    "description": {
      "content": "Limak has a grid that consists of 2 rows and _n_ columns. The _j_\\-th cell in the _i_\\-th row contains an integer _t__i_, _j_ which can be positive, negative or zero. A non-empty rectangle of cells i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF771E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Limak has a grid that consists of 2 rows and _n_ columns. The _j_\\-th cell in the _i_\\-th row contains an integer _t__i_, _j_ which can be positive, negative or zero.\n\nA non-empty rectangle of cells i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Limak 有一个由 #cf_span[2] 行和 #cf_span[n] 列组成的网格。第 #cf_span[i] 行第 #cf_span[j] 列的单元格包含一个整数 #cf_span[ti, j]，它可以是正数、负数或零。\n\n一个非空的矩形区域被称为 _nice_，当且仅当其中所有单元格的数字之和等于 #cf_span[0]。\n\nLimak 想要选择一些 nice 矩形并把它们作为礼物送给朋...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 300{,}000 $, be the number of columns.  \nLet $ T = (t_{i,j}) \\in \\mathbb{Z}^{2 \\times n} $ be a $ 2 \\times n $ grid of integers.  \n\nA *nice ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments