42 lines
1004 B
C++
42 lines
1004 B
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
typedef long long LL;
|
||
const LL INF = 1e17;
|
||
const int N = 1e6 + 10;
|
||
int n, p;
|
||
LL a[N]; // 每个小朋友的数字(读入)
|
||
LL b[N]; // 每个小朋友的特征(之前序列里的最大子段和)
|
||
LL c[N]; // 每个小朋友的分数(c[1]=b[1]，c[i]=c[k]+b[k])
|
||
int main() {
|
||
// 加快读入
|
||
ios::sync_with_stdio(false), cin.tie(0);
|
||
// 读入
|
||
cin >> n >> p;
|
||
for (int i = 1; i <= n; i++)
|
||
cin >> a[i];
|
||
|
||
// 求最大子段和
|
||
b[0] = -INF;
|
||
LL sum = 0;
|
||
for (int i = 1; i <= n; i++) {
|
||
sum += a[i];
|
||
b[i] = max(b[i - 1], sum);
|
||
sum = max(sum, (LL)0);
|
||
}
|
||
|
||
// 求分数
|
||
c[1] = b[1];
|
||
c[2] = c[1] + b[1];
|
||
for (int i = 3; i <= n; i++) {
|
||
c[i] = max(c[i - 1], c[i - 1] + b[i - 1]);
|
||
if (c[i] > c[1]) // 注意条件
|
||
c[i] %= p;
|
||
}
|
||
|
||
if (c[1] > 0) // 序列是不下降的,当c[1]>0时，c[n]>c[1]
|
||
cout << c[n] % p;
|
||
else
|
||
cout << max(c[n], c[1]) % p;
|
||
return 0;
|
||
}
|