Cod sursa(job #1027292)

Utilizator gegeadDragos Gegea gegead Data 12 noiembrie 2013 18:15:16
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<cstdio>
long long v[100001],c[100001],dq[100001],st=1,dr,t,s;

int dreapta(int i)
{
    long long min=v[i];
    int j=dr-1,u=i;
    while(st<=j)
    {
        if(v[dq[j]]+(i-dq[j])*s<=min)
        {
            min=v[dq[j]];
            u=dq[j];
        }
        --j;
    }
    return u;
}



inline void stanga(int i)
{
    if(i-dq[st]==t)
        ++st;
}


int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    int n,i,x;
    long long sum=0;
    scanf("%d%d%d",&n,&s,&t);
    for(i=1;i<=n;++i)
        scanf("%lld%lld",&v[i],&c[i]);
    dq[++dr]=1;
    for(i=2;i<=n;++i)
    {
        stanga(i);
        dq[++dr]=dreapta(i);
    }
    for(i=1;i<=n;++i)
        sum+=v[dq[i]]*c[i]+s*(i-dq[i])*c[i];
    printf("%lld",sum);
    return 0;
}