Pagini recente » Cod sursa (job #174399) | Cod sursa (job #673673) | Cod sursa (job #2910434) | Cod sursa (job #1651975) | Cod sursa (job #3127279)
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
int main()
{
std::ifstream file_in("branza.in");
std::ofstream file_out("branza.out");
long long n, s, t, cost = 0;
std::deque<long long> d;
file_in >> n >> s >> t;
std::vector<long long> c(n + 2), p(n + 2);
for (int i = 1; i <= n; i++) {
file_in >> c[i] >> p[i];
}
for (int i = 1; i <= n; i++) {
while (!d.empty() && (c[d.back()] + s * (i - d.back())) > c[i]) {
d.pop_back();
}
d.push_back(i);
while (!d.empty() && i - d.front() > t) {
d.pop_front();
}
cost = cost + p[i] * c[d.front()] + s * p[i] * (i - d.front());
}
file_out << cost;
file_in.close();
file_out.close();
return 0;
}