Cod sursa(job #358057)

Utilizator tranbachhaiTran Bach Hai tranbachhai Data 21 octombrie 2009 19:31:46
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include<stdio.h>
long n,t,poz[100010],cost[100010],deque[100010],c[100010],put[100010];
long long sum;
int s;
int main()
{
long i,p=1,u=0;
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%ld%d%ld",&n,&s,&t);
for (i=1;i<=n;++i)
{
	scanf("%ld%ld",&c[i],&put[i]);
	cost[i]=c[i]+s*(n-i+1);
}
for (i=1;i<=n;++i)
{
while(p<=u && cost[i]<cost[deque[u]])
	u--;
deque[++u]=i;
if(deque[p]<=i-t)
	p++;
poz[i]=deque[p];
}
for (i=1;i<=n;++i)
	{
		sum=sum+put[i]*(c[poz[i]]+(i-poz[i])*s);
	}
printf("%lld",sum);
return 0;
}