Cod sursa(job #3127030)

Utilizator AndreiKatsukiAndrei Dogarel AndreiKatsuki Data 7 mai 2023 09:54:52
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

int n, s, t;
long long res;

int main(){
    f >> n >> s >> t;
    int c, p;
    f >> c >> p;
    deque<pair<int, int>> dq;
    dq.push_back({c, 0});
    res += (c * p);
    for(int i = 1; i < n; ++i){
        f >> c >> p;
        if(!dq.empty() && dq.front().second + t < i){
            dq.pop_front();
        }
        while(!dq.empty() && (s * (i - dq.back().second) + dq.back().first) >= c){
            dq.pop_back();
        }
        dq.push_back({c, i});
        res += (p * dq.front().first + s * p * (i - dq.front().second));
    }
    g << res;
    return 0;
}