Cod sursa(job #2832788)

Utilizator mihaistamatescuMihai Stamatescu mihaistamatescu Data 14 ianuarie 2022 12:09:49
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <fstream>

using namespace std;
long long n, s, t, i, p, u, sol, d[100010], c[100010], P[100010];

int main() {
    ifstream fin("branza.in");
    ofstream fout("branza.out");
    fin >> n >> s >> t;
    for (i = 1; i <= n; i++) {
        fin >> c[i] >> P[i];
    }
    d[1] = 1;
    p = 1;
    u = 1;
    sol += c[1] * P[1];
    for (i = 2; i <= n; i++) {
        while (p <= u && c[i] <= (i - d[u]) * s + c[d[u]]) {
            u--;
        }
        d[++u] = i;
        if (i - d[p] == t + 1) {
            p++;
        }
        sol += (c[d[p]] + s * (i - d[p])) * P[i];
    }
    fout << sol;
    return 0;
}