Cod sursa(job #2708731)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 19 februarie 2021 11:47:57
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>

using namespace std;

const int N = 1e5;

long long cost[N], dq[N];

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

    long long n, s, t, ct, st, dr, tot = 0;
    in >> n >> s >> t;
    st = 0, dr = -1;
    for (int i = 0; i < n; ++i) {
        in >> cost[i] >> ct;
        if (st <= dr && dq[st] == i - t)
            ++st;
        while (st <= dr && cost[i] <= cost[dq[dr]] + s * (i - dq[dr]))
            --dr;
        dq[++dr] = i;
        tot += ct * (cost[dq[st]] + s * (i - dq[st]));
    }
    out << tot;

    in.close();
    out.close();
    return 0;
}