Cod sursa(job #2378370)

Utilizator carburatorMitica Carburator carburator Data 12 martie 2019 09:10:36
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
deque<long long>d;
long long N,S,T,pozi,i,C[100005],sum,P;
int main()
{
    //citire
    fin>>N>>S>>T;
    //punem in capatul dequelui toate variantele si, la introducerea alteia noi, le scoatem pe cele mai putin eficiente ca aceasta;
    //in fata vom avea mereu cea mai buna varianta;
    //nu uitam sa scoatem cele mai vechi de T
    for(i=1;i<=N;i++){
        fin>>C[i]>>P;
        while(!d.empty() && (C[d.back()] + S*(i-d.back()) > C[i])) d.pop_back();
        d.push_back(i);
        while(i-d.front() > T && !d.empty()) d.pop_front();
        sum+=(C[d.front()]+S*(i-d.front()))*P;
    }
    fout<<sum;
    return 0;
}