Cod sursa(job #251858)

Utilizator P1gl3TGilca Mircea Alexandru P1gl3T Data 3 februarie 2009 15:01:38
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include<stdio.h>
int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	const int N=100001;
	int n,s,t,i;
	long long sum=0;
	int deque[N],start,end;
	int c[N], p[N];
	scanf("%d%d%d",&n,&s,&t);
	for(i=1;i<=n;++i)
		scanf("%d%d",&c[i],&p[i]);
	start=1; end=0;
	for(i=1;i<=n;++i)
	{
		if(deque[start]==i-t-1) ++start;
		while(start<=end && c[deque[end]]+s*(i-deque[end])>=c[i]) --end;
		deque[++end]=i;
		sum+=p[i]*(c[deque[start]]+s*(i-deque[start]));
	}
	printf("%lld",sum);
	return 0;
}