/\*
这道题前50%的数据满足n<=1000，O(n^2)的算法就可以搞定
但100%的数据满足n<=1000000,需要O(n)的算法。所以考虑前缀和。
\*/
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,p,num[1000010],a[1000010],b[1000010],s[1000010],t1,t2;
int main(){
scanf("%lld%lld%lld",&n,&p,&num[1]);
a[1]=b[1]=num[1];
for(int i=2;i<=n;i++){
scanf("%lld",&num[i]);
num[i]+=num[i-1];
a[i]=max(num[i]-num[i-1],a[i-1]+num[i]-num[i-1]);//包含小朋友i的最大连续数字和
b[i]=max(b[i-1],a[i]);}//小朋友i及其之前的连续若干个数字之和的最大值（即特征值）
s[1]=b[1];s[2]=(s[1]+b[1]);
t1=b[1]/p;s[1]%=p;
for(int i=3;i<=n;i++){
s[i]=max(s[i-1],s[i-1]+b[i-1]);
t2+=s[i]/p;
s[i]%=p;
}
if(t1>t2||(t1==t2&&s[1]>=s[n]))printf("%lld\n",s[1]);//jsz大佬出来解释这一句！！！ 看不懂！！！
else printf("%lld\n",s[n]);
return 0;
}
```
by qscweadzx @ 2017-10-22 21:27:56
因为题目里面的第一个小盆友的特征值和分数就是它自己的数字，和后面其他小盆友的不同，所以应该输出s1和sn中的较大者。而我们在前面计算的时候就已经直接取模了，根据余数无法判断出两数原数的大小，所以我们每取一次余数，就将去掉的这几个p的个数都给保存着，所以真实的未取模的s1值应该是p\*t1+ｓ１，ｓ２值应是p\*t2+s2，而s1和s2都是不到p的，所以我们先比较两者p的个数t1和t2（这就相当于我们两数比大小先比较最高位，可以将这两个数看作是两个两位数，p进制的）
by jszjinshengzhi @ 2017-10-22 21:53:25
@[jszjinshengzhi](/space/show?uid=48343) 谢谢
by _Felix @ 2019-10-29 07:24:30