【BZOJ3544】[ONTAK2010]Creative Accounting 前缀和+set

【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

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;

}