Cod sursa(job #920966)

Utilizator timicsIoana Tamas timics Data 20 martie 2013 18:22:02
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<stdio.h>
long long n,s,t,c[100010],p[100010],m[100010],d[100010],ret=0;
int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%lld%lld%lld",&n,&s,&t);
    for(int i=1;i<=n;++i)
        scanf("%lld%lld",&c[i],&p[i]);
    int f=1;
    int b=0;
    for(int i=1;i<=n;++i)
    {
        while(f<=b && c[i]+(n-i)*s<c[d[b]]+(n-d[b])*s)
            --b;
        ++b;
        d[b]=i;
        if(d[f]==i-t-1)
            ++f;
        m[i]=c[d[f]]+(i-d[f])*s;
        ret=ret+m[i]*p[i];
    }
    printf("%lld",ret);
    return 0;
}