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