CF1788E.Sum Over Zero
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an array a1,a2,…,an 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≤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≤x≤b and c≤x≤d .
- For each [x,y] in S , ax+ax+1+…+ay≥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)=∑[x,y]∈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≤n≤2⋅105 ).
The next line is followed by n integers a1,a2,…,an ( −109≤ai≤109 ).
输出格式
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 a1+a2=0 and a4+a5=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)≤9 , the answer is 9 .
In the third example, S can only be an empty set, so the answer is 0 .