Cod sursa(job #209177)

Utilizator savimSerban Andrei Stan savim Data 21 septembrie 2008 11:23:28
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <stdio.h>
#define maxl 100010

long long n,s,t,i,st,dr;
long long brz[maxl][2];
long long deq[maxl];
long long cost;

int main() {
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);

    scanf("%lld %lld %lld",&n,&s,&t);
    for (i=1; i<=n; i++)
        scanf("%lld %lld",&brz[i][0],&brz[i][1]);

    st=1;t++;
    for (i=1; i<=n; i++) {

        if (i-t+1>deq[st]) st++;
        deq[++dr]=i;
        while (dr-1>=st && brz[deq[dr]][0]+s*(i-deq[dr]) < brz[deq[dr-1]][0]+s*(i-deq[dr-1])) {
            deq[dr-1]=deq[dr];
            dr--;
        }
        cost+=brz[deq[st]][0]*brz[i][1]+s*(i-deq[st])*brz[i][1];
    }
    
    printf("%lld\n",cost);

    return 0;
}