Cod sursa(job #238079)

Utilizator AndreyPAndrei Poenaru AndreyP Data 31 decembrie 2008 14:50:41
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.5 kb
#include<stdio.h>
#define N 100010
struct branza
{
	long long c,p;
};
branza a[N];
long long n,s,t,d[N],p=1,u;
long long rez;
int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%lld%lld%lld",&n,&s,&t);
	for(long long i=1; i<=n; ++i)
	{
		scanf("%lld%lld",&a[i].c,&a[i].p);
		while(p<=u && i-d[p]>t)
			++p;
		while(p<=u && s*(i-d[u])+a[d[u]].c>=a[i].c)
			--u;
		d[++u]=i;
		rez+=(a[d[p]].c+s*(i-d[p]))*a[i].p;
	}
	printf("%lld\n",rez);
	return 0;
}