Cod sursa(job #2719316)

Utilizator CaptnBananaPetcu Tudor CaptnBanana Data 9 martie 2021 19:24:13
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
/*
    https://infoarena.ro/problema/branza
*/

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e8;
int c[N];

int main(){
    int n, s, t, p;
    long long cost = 0;

    f >> n >> s >> t;
    t++;
    deque<int> dq;
    for(int i = 0; i < n; i++){
        f >> c[i] >> p;
        if(!dq.empty() && dq.front() == i - t)
            dq.pop_front();

        while(!dq.empty() && c[i] <= c[dq.back()] + s * (i - dq.back()))
            dq.pop_back();

        dq.push_back(i);
        cost += (long long)p * (c[dq.front()] + s * (i - dq.front()));
    }

    g << cost;
}