Cod sursa(job #74945)

Utilizator slayer4uVictor Popescu slayer4u Data 29 iulie 2007 20:33:31
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<stdio.h>
long long inc,sf,sum,total,i,t,n,s;
struct lol
{
	long long p,c;
};
lol x[100001];
struct loldoi
{
	long long val,poz;
};
loldoi dq[100001];
int main()
{
	freopen ("branza.in","rt",stdin);
	freopen ("branza.out","wt",stdout);

	scanf("%lld %lld %lld",&n,&s,&t);

	for (i=1;i<=n;i++)
		scanf("%lld %lld",&x[i].c,&x[i].p);

	inc=1;sf=0;
	for (i=1;i<=n;i++)
	{
		sum=x[i].c;
		sum+=(n-i)*s;

		while (sf>=inc && sum<=dq[sf].val) sf--;

		dq[++sf].val=sum,dq[sf].poz=i;

		if (i-dq[inc].poz>t) inc++;

		total+=(long long)(dq[inc].val-(n-dq[inc].poz)*s)*x[i].p+(i-dq[inc].poz)*s*x[i].p;
	}

	printf("%lld\n",total);
	return 0;
}