Cod sursa(job #67972)

Utilizator sealTudose Vlad seal Data 26 iunie 2007 10:55:19
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>
#define Nm 100000
int C[Nm],P[Nm],n,s,t;
unsigned long long Cm[Nm];

void read()
{
    int i;

    freopen("branza.in","r",stdin);
    scanf("%d%d%d",&n,&s,&t);
    for(i=0;i<n;++i)
        scanf("%d%d",C+i,P+i);
}

void solve()
{
    int Val[Nm],Poz[Nm],l=0,r=0,i;

    Cm[0]=(unsigned long long)C[0]*P[0]; Val[0]=C[0]; Poz[0]=0;
    for(i=1;i<n;++i)
    {
        while(l<=r && C[i]<=Val[r]+s*i)
            --r;
        Val[++r]=C[i]-s*i; Poz[r]=i;
        if(Poz[l]==i-t-1)
            ++l;
        Cm[i]=Cm[i-1]+(Val[l]+s*i)*(unsigned long long)P[i];
    }
}

void write()
{
    freopen("branza.out","w",stdout);
    printf("%llu\n",Cm[n-1]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}