Mai intai trebuie sa te autentifici.
Cod sursa(job #2799186)
| Utilizator | Data | 12 noiembrie 2021 16:51:33 | |
|---|---|---|---|
| Problema | Branza | Scor | 40 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.93 kb |
#include <fstream>
#include <deque>
using namespace std;
const int Nmax = 1e5;
unsigned long long c[1 + Nmax], p[1 + Nmax];
deque<int> dq;
int main() {
ifstream fin("branza.in");
ofstream fout("branza.out");
int n;
long long s, t;
fin >> n >> s >> t;
for (int i = 1; i <= n; i++) {
fin >> c[i] >> p[i];
}
unsigned long long ans = 0;
for (int i = 1; i <= t; i++) {
while (!dq.empty() && c[dq.back()] + (i - dq.back()) * s >= c[i]) {
dq.pop_back();
}
dq.push_back(i);
ans += (c[dq.front()] + (i - dq.front()) * s) * p[i];
}
for (int i = t + 1; i <= n; i++) {
if (!dq.empty() && dq.front() == i - t) {
dq.pop_front();
}
while (!dq.empty() && (c[dq.back()] + (i - dq.back()) * s) * p[i] >= c[i] * p[i]) {
dq.pop_back();
}
dq.push_back(i);
ans += (c[dq.front()] + (i - dq.front()) * s) * p[i];
}
fout << ans;
return 0;
}
