BZOJ3544 [ONTAK2010]Creative Accounting

2015.01.16 08:10 Fri| 0 visits oi_2015| 2015_刷题日常| Text

Solution

(貌似有人看不懂题?

给定一个长度为N的数组a和M,求一个区间[l,r],使得 $(\sum_{i=l}^{r}{a_i}) \mod M$ 的值最大,求出这个值,注意这里的 mod 是数学上的 mod。

维护一个前缀和。每一次使用前缀和 $s_i$ 以及 $s_i$ 减去 $s_1$ 与 $s_{i-1}$ 之间大于 $s_i$ 的最小值更新答案。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 200005

long long n, mod, ans, a[N], sum[N];
set<long long> s;
set<long long>::iterator it;

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> mod;
    for (int i = 1; i <= n; ++i)
        cin >> a[i],
        a[i] = (a[i] % mod + mod) % mod,
        sum[i] = (sum[i - 1] + a[i]) % mod;
    for (int i = 1; i <= n; ++i)
    {
        ans = max(ans, sum[i]);
        if ((it = s.upper_bound(sum[i])) != s.end())
            ans = max(ans, sum[i] - *it + mod);
        s.insert(sum[i]);
    }
    cout << ans << endl;
}