【BZOJ3544】[ONTAK2010]Creative Accounting
Description
给定一个长度为N的数组a和M，求一个区间[l,r]，使得(\sum_{i=l}^{r}{a_i}) mod M的值最大，求出这个值，注意这里的mod是数学上的mod
Input
第一行两个整数N，M。
第二行N个整数a_i。
Output
输出一行，表示答案。
Sample Input
5 13
10 9 5 -5 7
10 9 5 -5 7
Sample Output
11
HINT
【数据范围】
N<=200000，M,a_i<=10^18
题解：首先子串和=两个前缀相减。所以对于每个前缀和，我们找到max（它-之前的前缀）就行了。贪心可知之前的前缀和要么是它的后继要么是0。
#include <cstdio>
#include <cstring>
#include <set>
#include <iostream>
using namespace std;
typedef long long ll; set<ll> s;
set<ll>::iterator it;
ll m,sum,ans;
int n;
inline ll rd()
{
ll ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd();
int i;
s.insert(0);
for(i=1;i<=n;i++)
{
sum=((sum+rd())%m+m)%m;
it=s.upper_bound(sum);
if(it!=s.end()) ans=max(ans,sum+m-(*it));
s.insert(sum);
ans=max(ans,sum);
}
printf("%lld",ans);
return 0;
}