Pagini recente » Cod sursa (job #1255231) | Cod sursa (job #310420) | Cod sursa (job #789992) | Cod sursa (job #572693) | Cod sursa (job #3151128)
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
InParser cin("branza.in");
ofstream cout("branza.out");
#define int long 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;
}
};
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.empty() && dq.front().idx < i-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;
}