Cod sursa(job #358065)

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