Cod sursa(job #2063819)
Utilizator | Matei 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;
}