A15724. Sum Over Zero
编程题
普及/提高-
知识点
题目描述
You are given an array $a_1, a_2, \ldots, a_n$ of $n$ integers. Consider $S$ as a set of segments satisfying the following conditions.
- Each element of $S$ should be in form $[x, y]$ , where $x$ and $y$ are integers between $1$ and $n$ , inclusive, and $x \leq y$ .
- No two segments in $S$ intersect with each other. Two segments $[a, b]$ and $[c, d]$ intersect if and only if there exists an integer $x$ such that $a \leq x \leq b$ and $c \leq x \leq d$ .
- For each $[x, y]$ in $S$ , $a_x+a_{x+1}+ \ldots +a_y \geq 0$ .
The length of the segment $[x, y]$ is defined as $y-x+1$ . $f(S)$ is defined as the sum of the lengths of every element in $S$ . In a formal way, $f(S) = \sum_{[x, y] \in S} (y - x + 1)$ . Note that if $S$ is empty, $f(S)$ is $0$ .
What is the maximum $f(S)$ among all possible $S$ ?
- Each element of $S$ should be in form $[x, y]$ , where $x$ and $y$ are integers between $1$ and $n$ , inclusive, and $x \leq y$ .
- No two segments in $S$ intersect with each other. Two segments $[a, b]$ and $[c, d]$ intersect if and only if there exists an integer $x$ such that $a \leq x \leq b$ and $c \leq x \leq d$ .
- For each $[x, y]$ in $S$ , $a_x+a_{x+1}+ \ldots +a_y \geq 0$ .
The length of the segment $[x, y]$ is defined as $y-x+1$ . $f(S)$ is defined as the sum of the lengths of every element in $S$ . In a formal way, $f(S) = \sum_{[x, y] \in S} (y - x + 1)$ . Note that if $S$ is empty, $f(S)$ is $0$ .
What is the maximum $f(S)$ among all possible $S$ ?
输入格式
The first line contains one integer $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ).
The next line is followed by $n$ integers $a_1, a_2, \ldots, a_n$ ( $-10^9 \leq a_i \leq 10^9$ ).
The next line is followed by $n$ integers $a_1, a_2, \ldots, a_n$ ( $-10^9 \leq a_i \leq 10^9$ ).
输出格式
Print a single integer, the maximum $f(S)$ among every possible $S$ .
输入输出样例
输入 #1
5 3 -3 -2 5 -4
输出 #1
4
输入 #2
10 5 -2 -4 -6 2 3 -6 5 3 -2
输出 #2
9
输入 #3
4 -1 -2 -3 -4
输出 #3
0
说明/提示
In the first example, $S=\{[1, 2], [4, 5]\}$ can be a possible $S$ because $a_1+a_2=0$ and $a_4+a_5=1$ . $S=\{[1, 4]\}$ can also be a possible solution.
Since there does not exist any $S$ that satisfies $f(S) > 4$ , the answer is $4$ .
In the second example, $S=\{[1, 9]\}$ is the only set that satisfies $f(S)=9$ . Since every possible $S$ satisfies $f(S) \leq 9$ , the answer is $9$ .
In the third example, $S$ can only be an empty set, so the answer is $0$ .
Since there does not exist any $S$ that satisfies $f(S) > 4$ , the answer is $4$ .
In the second example, $S=\{[1, 9]\}$ is the only set that satisfies $f(S)=9$ . Since every possible $S$ satisfies $f(S) \leq 9$ , the answer is $9$ .
In the third example, $S$ can only be an empty set, so the answer is $0$ .