Pagini recente » Cod sursa (job #3317098) | Cod sursa (job #3356749) | Cod sursa (job #3354904) | Cod sursa (job #3326282) | Cod sursa (job #3339207)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
#define in fin
#define out fout
#define int long long
ifstream fin("branza.in");
ofstream fout("branza.out");
const int MAXN = 1e5;
int n, s, t, total;
int cost[MAXN+1], cerere[MAXN+1];
deque<int> dq;
signed main() {
in >> n >> s >> t;
for (int i = 1; i <= n; i++)
in >> cost[i] >> cerere[i];
// costul pastrarii unei branze de la ziua i la ziua j este
// cost[i] + s * (j - i). in intervalul (i - t, i) cautam minimul dupa formula aia
for (int i = 1; i <= n; i++) {
while (!dq.empty() && dq.front() < i - t)
dq.pop_front();
while (!dq.empty() && cost[i] <= cost[dq.back()] + s * (i - dq.back()))
dq.pop_back();
dq.push_back(i);
total += cost[dq.front()] * cerere[i] + s * cerere[i] * (i - dq.front());
}
out << total;
return 0;
}