【bzoj3544】[ONTAK2010]Creative Accounting

2015年2月28日1,3072

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

题解

水水更健康

维护前缀和,对于每个前缀和,用set找第一个其大的数,找不到就取set中最小的数,然后将当前前缀和加入set

 

  • 广大圆明2016年3月13日 下午3:08 回复

    为什么ans的初值是0啊,为何不是-inf

    #1  
    • hzwer2016年3月25日 下午10:39 回复
      admin

      你说的很有道理。。。

      #11