记录编号	22434	评测结果	AAAAAAAAAA
题目名称	求和	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	1.252 s
提交时间	2010-11-19 11:35:01	内存使用	2.17 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

int ans,n,k,pp,s[100001];

struct treap
{
public:
	struct node
	{
		int v,fix;
		node *l,*r;
	}p[100002],*root;

	int size,pn;
	treap()
	{
		srand(1108);
		size=0;
		pn=0;
		root=NULL;
	}
	
	void rotr(node *&tk)
	{
		node *q=tk;
		tk=q->l;
		q->l=tk->r;
		tk->r=q;
	}
	
	void rotl(node *&tk)
	{
		node *q=tk;
		tk=q->r;
		q->r=tk->l;
		tk->l=q;
	}
	
	void inspoint(int v,node *&tk)
	{
		if (tk==NULL)
		{
			pn++;
			p[++size].fix=rand();
			p[size].v=v;
			tk=&p[size];
		}
		else
		{
			if (v < tk->v)
			{
				inspoint(v,tk->l);
				if (tk->l->fix < tk->fix)
					rotr(tk);
			}
			else
			{
				inspoint(v,tk->r);
				if (tk->r->fix < tk->fix)
					rotl(tk);
			}
		}
	}
	
	int findxp(int v)
	{
		node *now=root;
		node *tmp;
		tmp=NULL;
		while (now!=NULL)
		{
			if (now->v <= v)
			{
				tmp=now;
				now=now->r;
			}
			else	now=now->l;
		}
		if (tmp) return tmp->v;
		return -1;
	}
	
	int finddp(int v)
	{
		node *now=root;
		node *tmp;
		tmp=NULL;
		while (now!=NULL)
		{
			if (now->v >= v)
			{
				tmp=now;
				now=now->l;
			}
			else	now=now->r;
		}
		if (tmp) return tmp->v;
		return -1;
	}
	
	void printpoint(node *tk)
	{
		if (tk)
		{
			printpoint(tk->l);
			printf("%d ",tk->v);
			printpoint(tk->r);
		}
	}
	
	void ins(int v)
	{ 
		inspoint(v,root);
	}
	
	void print()
	{ 
		printpoint(root);
		printf("\n");
	}
}tree;


int main()
{
	freopen("suma.in","r",stdin);
	freopen("suma.out","w",stdout);
	scanf("%d%d%d",&n,&k,&pp);ans=1000000000;
	
	for (int i=1;i<=n;i++)
	{
		scanf("%d",s+i);
		s[i]+=s[i-1];
		s[i]%=pp;
	}
	
	tree.ins(0);
	for (int i=1;i<=n;i++)
	{
		int t1=tree.findxp(s[i]-k);
		int t2=tree.findxp(pp-k+s[i]);
		if (t1!=-1 && ans>s[i]-t1) ans=s[i]-t1;
		if (t2!=-1 && ans>s[i]-t2+pp) ans=s[i]-t2+pp;
		tree.ins(s[i]);
	}
	printf("%d\n",ans);
	return 0;
}