Cod sursa(job #334960)

Utilizator ZillaMathe Bogdan Zilla Data 28 iulie 2009 12:24:50
Problema Branza Scor 100
Compilator cpp Status done
Runda splunge5 Marime 0.66 kb
#include <stdio.h>

#define Nmax 100100

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

struct coada{
    long long nr,poz;
};

coada q[Nmax];

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