Mai intai trebuie sa te autentifici.
Cod sursa(job #74885)
| Utilizator | Data | 29 iulie 2007 11:49:47 | |
|---|---|---|---|
| Problema | Branza | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.63 kb |
#include <stdio.h>
#define NMAX 100002
long int n,i,j,k,s,a[NMAX],D[NMAX][2],st,dr,T,c[NMAX];
long long sol;
int main()
{
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",&a[i],&c[i]);
D[1][0]=a[1];D[1][1]=1;
sol=a[1]*c[1];
st=1;dr=1;
for (i=2;i<=n;i++)
{
for (;(st<dr)&&(D[st][1]<i-T);st++);
for (;(dr>=st)&&(a[i]<D[dr][0]+(i-D[dr][1])*s);dr--);
D[++dr][0]=a[i];
D[dr][1]=i;
sol=sol+((long long) D[st][0]+(long long) (i-D[st][1])*s)*c[i];
}
printf("%lld",sol);
return 0;
}
