Cod sursa(job #209176)

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

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

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

    scanf("%d %d %d",&n,&s,&t);
    for (i=1; i<=n; i++)
        scanf("%d %d",&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;
}