Cod sursa(job #334949)

Utilizator ZillaMathe Bogdan Zilla Data 28 iulie 2009 12:19:07
Problema Branza Scor 0
Compilator cpp Status done
Runda splunge5 Marime 0.62 kb
#include <stdio.h>

#define Nmax 100100

int n,s,t,inc=1,sf=0,cost;

struct coada{
    int nr,poz;
};

coada q[Nmax];

int main()
{
    int i,x,y;
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout); 
    scanf("%d%d%d",&n,&s,&t);
    for(i=1;i<=n;++i)
        {
            scanf("%d%d",&x,&y);
			while(q[inc].poz <=i-t && inc<=sf)
                ++inc;
			while(inc<=sf && ((i-q[sf].poz)*s+q[sf].nr)>x)
                --sf;
            q[++sf].poz=i;
            q[sf].nr=x;
            cost+=y*(q[inc].nr+s*(i-q[inc].poz));
        }
    printf("%d",cost); 
    return 0;
}