Cod sursa(job #74885)

Utilizator devilkindSavin Tiberiu devilkind 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;
}