Pagini recente » Cod sursa (job #2140729) | Cod sursa (job #876107) | Cod sursa (job #1949922) | Cod sursa (job #304143) | Cod sursa (job #937911)
Cod sursa(job #937911)
#include <fstream>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
#define pb push_back
#define rm_front(D) while(!D.empty() && D.front() < i - lifetime)D.pop_front()
#define rm_back(D) while(!D.empty() && cost[i] < cost[D.back()] + extra * (i - D.back()))D.pop_back()
const int maxn = 100100;
typedef long long LL;
LL cost[maxn],req[maxn];
LL best[maxn];
deque<int> D;
int main()
{
LL n,extra,lifetime,i;
LL now,before;
in >> n >> extra >> lifetime;
for(i=1;i<=n;++i)
in >> cost[i] >> req[i];
best[1] = cost[1]*req[1];
D.pb(1);
for(i=2;i<=n;++i){
rm_front(D);
rm_back(D);
D.pb(i);
now = cost[i];
before = cost[D.front()] + extra * (i - D.front());
best[i] = 1LL*min(now,before) * req[i];
}
unsigned long long show = 0;
for(i=1;i<=n;++i)
show += best[i];
out << show << "\n";
return 0;
}