Cod sursa(job #932759)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 29 martie 2013 11:05:50
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<iostream>
#include<fstream>
using namespace std;

#define NMAX 100001

int c[NMAX],p[NMAX],deque[NMAX];
long long d[NMAX];

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

int main ()
{
    int i,st,dr,n,s,t;
    ifstream f("branza.in");
    ofstream g("branza.out");
    f>>n>>s>>t;
    for(i=1;i<=n;i++)
        f>>c[i]>>p[i];
    f.close();
    st=1;
    dr=1;
    d[1]=c[1]*p[1];
    deque[st]=1;
    for(i=2;i<=n;i++) {
        d[i]=0LL+minim(c[i]*p[i],s*p[i]*(i-deque[st])+c[deque[st]]*p[i])+d[i-1];
        while(st<=dr && c[i]<c[deque[dr]]+s*(i-deque[dr]))
            dr--;
        deque[++dr]=i;
        if(i-deque[st]+1>t)
            st++;
    }
    g<<d[n];
    g.close();
    return 0;
}