Cod sursa(job #2063819)

Utilizator MateiTrandafirMatei Trandafir MateiTrandafir Data 11 noiembrie 2017 15:17:15
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.49 kb
#include <fstream>

int d[100000], st = 0, dr = -1, v[100000];

int main() {
    std::ifstream in("branza.in");
    std::ofstream out("branza.out");
    int n, s, t, c;
    long long r = 0;
    in >> n >> s >> t;
    for (int i = 0; i < n; ++i) {
        in >> v[i] >> c;
        if (i - d[st] > t) ++st;
        while (dr > st && v[d[dr]] + s * (i - d[dr]) >= v[i]) --dr;
        r += c * ((long long) std::min(v[i], v[d[dr]] + s * (i - d[dr])));
        d[++dr] = i;
    }
    out << r;
    return 0;
}