Cod sursa(job #382195)

Utilizator liv182copoiu liviu liv182 Data 13 ianuarie 2010 09:22:07
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<stdio.h>
int dq[1<<17],st=1,dr=0,t,s;
int cost[1<<17],kg[1<<17];
long long sum=0;
inline void stanga (int i)
{
	if(i-dq[st]==t)
		++st;
}
void dreapta(int i)
{
	while(st<=dr && cost[i]<=cost[dq[dr]]+s*(i-dq[dr]))
	
		--dr;
	dq[++dr]=i;
	
}
int main()
{
	int n,t;
	
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%d%d%d",&n,&s,&t);
	++t;
	for(int i=1;i<=n;++i)
		scanf("%d%d",&cost[i],&kg[i]);
	for(int i=1;i<t;++i)
		dreapta(i);
	for(int i=t;i<=n;++i)
	{
		stanga(i);
		dreapta(i);
		sum=sum+(long long)(cost[dq[st]]+s*(i-dq[st]))*(long long)kg[i];
	}
	printf("%d",sum);
	return 0;
}