AC代码：

 https://codeforces.com/contest/1788/submission/195085759

题意：

给你一个n个整数的数组a1，a2，…，an。将S视为满足以下条件的一组线段。

1. S的每个元素都应该是[x，y]形式，其中x和y是1和n之间的整数，包括1和n，x≤y。

2. S中没有两个线段彼此相交。两段[a，b]和[c，d]相交当且仅当存在整数x使得a≤x≤b且c≤x≤d。

3. 对于S中的每个[x，y]，ax+ax+1+…+ay≥0。

线段[x，y]的长度定义为y−x+1。f(S)被定义为S中每个元素的长度之和。

形式定义，f(S)=∑[x，y]∈S（y−x+1）。

注意，如果S为空，则f(S)为0。

题解：

DP + 前缀和 + 树状数组