Cod sursa(job #2811770)

Utilizator Chivu_RazvanChivu Razvan Chivu_Razvan Data 3 decembrie 2021 08:50:03
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

long long c[100001], p[100001];

int main() {
    ifstream fin("branza.in");
    ofstream fout("branza.out");

    int n, s, t;
    fin >> n >> s >> t;
    for(int i = 1; i <= n; i++)
        fin >> c[i] >> p[i];

    int ans = 0;
    deque <int> d;
    for(int i = 1; i <= n; i++) {
        while(!d.empty() && c[i] <= c[d.back()] + s * (i - d.back()))
            d.pop_back();

        d.push_back(i);

        while(!d.empty() && d.front() < i - t)
            d.pop_front();

        ans += p[i] * (c[d.front()] + s * (i - d.front()));

    }

    fout << ans;

    return 0;
}