Pagini recente » Cod sursa (job #757844) | Cod sursa (job #2454037) | Cod sursa (job #1774770) | Cod sursa (job #2017721) | Cod sursa (job #2155253)
#include<fstream>
#include<deque>
using namespace std;
ifstream in ("branza.in");
ofstream out ("branza.out");
int n,s,t,x,sum,cost[100001],cant[100001],v[100001];
deque<int> w;
int main (void) {
in >> n >> s >> t;
for (int i = 1; i <= n; i ++) {
in >> cost[i] >> cant[i];
}
for (int i = 1; i <= n; i ++) {
if (w.empty() == 0) {
sum += min (cost[i],cost[w.front()]+s*(i-w.front()) ) * cant[i];
}
else {
sum += cost[i] * cant[i];
}
x = cost[i] + s*(n-i+1);
while (w.empty() == 0 && x < v[w.back()]) {
w.pop_back();
}
w.push_back(i);
v[i] = x;
if (w.front() < i-t) {
w.pop_front();
}
}
out << sum;
return 0;
}