可以发现,下面我的代码是有很大问题的:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,mod,maxv,ans=-1e18-7,nowmaxv=-1e18-7;
int a[1000005],dp[1000005],score[1000005];
signed main()
{
cin>>n>>mod;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) dp[i]=(max(dp[i-1]+a[i],a[i]));
for (int i=1;i<=n;i++)
{
nowmaxv=max(nowmaxv,dp[i]);
dp[i]=nowmaxv;
}
score[1]=dp[1];
maxv=(dp[1]+score[1]);
for (int i=1;i<=n;i++) dp[i]=dp[i]%mod;
for (int i=2;i<=n;i++)
{
score[i]=maxv;
maxv=max(maxv,score[i]+dp[i]);
}
for (int i=1;i<=n;i++) ans=(max(ans,score[i]));
cout<<ans%mod<<endl;
return 0;
}
代码第21行中用了模,那么第25行比较大小显然会出问题,而却给了本蒟蒻AC?!
所以,建议以添加一组Hack数据,干掉本蒟蒻的程序。