Cod sursa(job #920953)

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