Cod sursa(job #933199)

Utilizator thebest001Neagu Rares Florian thebest001 Data 29 martie 2013 18:05:06
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>

long long d[100001], c[100001],p[100001],deque[100001];
int st=1,dr=0,n,s,t;

void stanga(int i){
    if(i-deque[st]+1>t)
        st++;
}
void dreapta(int i){
    while(st<=dr && c[i]<0LL+c[deque[dr]]+s*(i-deque[dr]))
        dr--;
}

inline long long minim(long long a, long long b)
{
    if(a<=b)
        return a;
    return b;
}

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("%lld %lld",&c[i],&p[i]);
        if (i>1)d[i]=0LL+minim(c[i]*p[i],1LL*s*p[i]*(i-deque[st])+c[deque[st]]*p[i])+d[i-1];
        else
            d[1]=c[i]*p[i];
        stanga(i);
        dreapta(i);
        deque[++dr]=i;

    }
    printf("%lld",d[n]);
    return 0;
}