Cod sursa(job #1919139)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 9 martie 2017 18:05:39
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
# include <fstream>
# include <deque>
# define DIM 100010
# define INF 1000000000000000000LL
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
deque<long long > d;
int i;
long long v[DIM],s,n,t,x,y,sol;
int main () {
    fin>>n>>s>>t;
    for(i=1;i<=n;i++){
        fin>>v[i]>>y;
        while(!d.empty()&&v[i]<v[d.back()]+s*(i-d.back()))
            d.pop_back();
        d.push_back(i);
        if(i-d.front()>t)
            d.pop_front();
        sol+=y*(v[d.front()]+s*(i-d.front()));
    }
    fout<<sol<<"\n";
    return 0;
}