Cod sursa(job #936300)

Utilizator Athena99Anghel Anca Athena99 Data 6 aprilie 2013 17:54:21
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>
#include <cassert>

const int nmax=100010;
int deque[nmax],p[nmax],c[nmax];
long long d[nmax];

int main()
{
    int n=0,s=0,t=0,i=0,u=0,x=1;
    long long sum=0;

    assert(freopen("branza.in","r",stdin));
    assert(freopen("branza.out","w",stdout));

    assert(scanf("%d%d%d",&n,&s,&t));

    for(i=1; i<n+1; ++i)
        assert(scanf("%d%d",&c[i],&p[i]));

    for(i=1; i<n+1; ++i)
    {
        while(c[i]<(c[deque[u]]+(i-deque[u])*s) && x<u+1)
            --u;

        deque[++u]=i;

        if(deque[x]+t<i)
            ++x;

        d[i]=c[deque[x]]+(i-deque[x])*s;
    }

    for(i=1; i<n+1; ++i)
        sum=sum+d[i]*p[i];

    assert(printf("%lld\n",sum));

    return 0;
}