Pagini recente » Cod sursa (job #432784) | Cod sursa (job #630564) | Cod sursa (job #2298232) | Cod sursa (job #104480) | Cod sursa (job #3150836)
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream cin("branza.in");
ofstream cout("branza.out");
#define int unsigned long
struct Info {
int price;
int to_beBought;
};
struct InfoDeque {
int val;
int idx;
InfoDeque() {}
InfoDeque(int val,int idx) {
this->val = val;
this->idx = idx;
}
bool operator<(InfoDeque a2) const {
return val<a2.val;
}
};
int n,price_toKeepPerKg,maxPeriodToKeep;
vector<Info> v;
void read() {
cin>>n>>price_toKeepPerKg>>maxPeriodToKeep;
v.resize(n+1);
for(int i=1;i<=n;i++) {
cin>>v[i].price>>v[i].to_beBought;
}
}
void solve() {
deque<InfoDeque> dq;
vector<int> dp(n+1);
for(int i=1;i<=n;i++) {
while(!dq.empty() && dq.back().val >= v[i].price + (n-i+1) * price_toKeepPerKg) {
dq.pop_back();
}
while(dq.size() > maxPeriodToKeep) {
dq.pop_front();
}
dq.push_back((*new InfoDeque(v[i].price + (n-i+1) * price_toKeepPerKg, i)));
dp[i] = min(v[i].price, v[dq.front().idx].price + ((i-dq.front().idx) * price_toKeepPerKg));
}
int rs=0;
for(int i=1;i<=n;i++) {
rs+=dp[i] * v[i].to_beBought;
}
cout<<rs;
}
int32_t main() {
read();
solve();
return 0;
}