Cod sursa(job #2727850)

Utilizator StefaniaCriStefania Cristea StefaniaCri Data 22 martie 2021 15:59:19
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream f ("branza.in");
ofstream g ("branza.out");
int main(){
    deque <long long> d;
    long long n,s,t;
    long long minim=0;
    f>>n>>s>>t;
    long long c[n+10],p[n+10];
    for(int i=0;i<n;i++){
        f>>c[i]>>p[i];
        while(!d.empty()&&(c[i]<=c[d.back()]+(i-d.back())*s))
          d.pop_back();
        while(!d.empty()&&(i-d.front()>t))
          d.pop_front();
        d.push_back(i);
        minim=minim+p[i]*(c[d.front()]+(i-d.front())*s);
    }
    g << minim << endl;
    return 0;
}