Cod sursa(job #920956)
Utilizator | Ioana Tamas timics | Data | 20 martie 2013 18:16:23 |
---|---|---|---|
Problema | Branza | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.58 kb |
#include<stdio.h>
int n,s,t,c[100010],p[100010],m[100010],d[100010];
long long ret;
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",&c[i],&p[i]);
int f=1;
int b=0;
for(int i=1;i<=n;++i)
{
while(f<=b && c[i]+(n-i)*s<=c[d[b]]+(n-d[b])*s)
--b;
++b;
d[b]=i;
if(d[f]==i-t)
++f;
m[i]=c[d[f]]+(i-d[f])*s;
ret=ret+1LL*m[i]*p[i];
}
printf("%lld",ret);
return 0;
}