Cod sursa(job #2732125)

Utilizator paulaalexandrescuPaula Alexandrescu paulaalexandrescu Data 28 martie 2021 19:08:05
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
long long N, C[100005], P, S, T, Suma;
deque<int> deq;

int main(){
    Suma = 0;
    fin>>N>>S>>T;
    T++;
    for(long long i=0; i<N; i++){
        fin>>C[i]>>P;
        if(deq.empty()!=0 && deq.front()==i-T) deq.pop_front();
        while(!deq.empty() && (C[deq.back()]+S*(i-deq.back()))>=C[i]) deq.pop_back();
        deq.push_back(i);
        Suma=Suma+(long long)P*(C[deq.front()]+S*(i-deq.front()));
    }
    fout<<Suma;
    return 0;
}