Cod sursa(job #932763)

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

#define NMAX 100001

long long d[NMAX], c[NMAX],p[NMAX],deque[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],1LL*s*p[i]*(i-deque[st])+c[deque[st]]*p[i])+d[i-1];
        while(st<=dr && c[i]<0LL+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;
}