Cod sursa(job #2853412)

Utilizator Chiri_Robert Chiributa Chiri_ Data 20 februarie 2022 11:34:18
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

using ull = unsigned long long;

ull n, t, s, sum;
ull c[100001], p[100001];
deque<int> d;

int cost(int ind, int nr, int zi) {
    // fout << zi << "  " << ind << " " << nr << " | ";
    if (ind == zi) {
        // fout << nr * c[ind] << '\n';
        return nr * c[ind];
    }
    int zile = zi - ind;
    // fout << nr * (zile * s + c[ind]) << '\n';
    return nr * (zile * s + c[ind]);
}

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

        while (!d.empty() && cost(d.back(), p[i], i) > cost(i, p[i], i)) {
            d.pop_back();
        }
        d.push_back(i);

        if (i - d.front() == t + 1) {
            d.pop_front();
        }

        sum += cost(d.front(), p[i], i);
        // fout << "\n\n";
    }
    fout << sum;
}