Pagini recente » Cod sursa (job #2719297) | Cod sursa (job #272730) | Cod sursa (job #591735) | Cod sursa (job #2068423) | Cod sursa (job #2452093)
#include <fstream>
#include <deque>
#include <vector>
#define nmax 100005
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int N, tax, sapt;
deque <int> dq;
vector <pair<int, int>> v;
int depo(int a, int b){
int rest = 0;
for(int i = b; i>a; i--)
rest+=v[i].second;
int suma = v[a].first * v[b].second + tax * rest;
return suma;
}
int main(){
in >> N >> tax >> sapt;
for(int i = 0; i<N; i++){
int pret, cant;
in >> pret >> cant;
v.push_back(make_pair(pret, cant));
}
int suma = 0;
for(int i = 0; i<N; i++){
while(!dq.empty() && v[i].first < v[dq.front()].first) dq.pop_front();
dq.push_front(i);
if(dq.back() < i - sapt) dq.pop_back();
if(depo(dq.back(), i) < v[i].first * v[i].second)
suma+=depo(dq.back(), i);
else
suma+=v[i].first * v[i].second;
}
out << suma;
return 0;
}