记录编号	326051	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013PJ]小朋友的数字	最终得分	100
用户昵称	Lethur	是否通过	通过
代码语言	C++	运行时间	0.742 s
提交时间	2016-10-20 19:17:26	内存使用	30.83 MiB

#include<iostream>
#include<cstdio> 
using namespace std;
long long maxx,a[1000001],n,m,p,f[1000001]={0},b[1000001],ff[1000001],ans;
bool zf;
int main()
{
	freopen("number2013.in","r",stdin);
	freopen("number2013.out","w",stdout); 
    cin>>n>>p;
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    f[1]=a[1];maxx=a[1];
    ff[1]=a[1];
    for (int i=2;i<=n;i++)
      {
        f[i]=max(f[i-1]+a[i],a[i]);
        ff[i]=max(maxx,f[i]);
        maxx=ff[i];
     }
    b[1]=ff[1];
    b[2]=ff[1]+b[1];
    if (b[2]>=b[1]) zf=true;
    maxx=b[2];
    for (int i=3;i<=n;i++)
      {
         if (ff[i-1]>0)
           {
             b[i]=b[i-1]+ff[i-1];
             if (b[i]>b[1]) zf=true;
             if (b[i]>1000000000) b[i]%=p;
           }
         else
             b[i]=b[2];  
      }
    if (!zf) ans=b[1];
    else ans=b[n];
    ans%=p; 
    printf("%lld",ans);        
}