Cod sursa(job #3127034)

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

using namespace std;

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

long long res, n, s, t;

int main(){
    f >> n >> s >> t;
    long long c, p;
    f >> c >> p;
    deque<pair<long long, long long>> dq;
    dq.push_back({c, 0});
    res += (c * p);
    for(long long 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;
}