Cod sursa(job #238077)

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