#P3544. [ONTAK2010]Creative Accounting

    ID: 2754 传统题 1000ms 128MiB 尝试: 796 已通过: 257 难度: 4 上传者: 标签>CF1600普及+/提高-一维前缀和同余的加减乘运算有序集合BySbullet

[ONTAK2010]Creative Accounting

题目描述

给定一个长度为 nn 的数组 aa 和 mm,求一个区间 [l,r][l,r],使得 (∑i=lrai) mod M(\sum_{i=l}^{r}a_i) \bmod M 的值最大。

输入格式

第一行两个整数 nn,mm。

第二行 nn 个整数 aia_i。

输出格式

输出一行一个整数,表示答案。

5 13
10 9 5 -5 7
11

提示

n≤2×105, m,ai≤1018n \le 2 \times 10^5,~m,a_i \le 10^{18}

题目来源

By Sbullet