Pagini recente » Cod sursa (job #2297622) | Cod sursa (job #1897888) | Cod sursa (job #2847479) | Cod sursa (job #568936) | Cod sursa (job #2884986)
#include <fstream>
#include <iostream>
#include <deque>
#define FILE "branza"
using namespace std;
ifstream fin(FILE".in");
ofstream fout(FILE".out");
struct element{
long long kg;
long long cost;
long long sapt;
};
deque<element> q;
int n,t,s,c,p,sum;
element array[1000000];
int main(){
fin >> n >> s >> t;
for(int i = 0; i < n; ++i){
fin >> array[i].cost >> array[i].kg;
array[i].sapt = i;
}
for(int i = n-1; i >= 0; --i){
while(!q.empty() && array[i].cost + s * (q.back().sapt - i) < q.back().cost && (q.back().sapt - i) <= t){
sum += s * (q.back().sapt - i) * q.back().kg;
element e;
e.kg = q.back().kg;
e.cost = array[i].cost;
e.sapt = 100000;
q.push_front(e);
q.pop_back();
}
while(!q.empty() && q.front().sapt-t+1 >= i){
//cout << q.front().kg << ' ' << q.front().cost << '\n';
sum += q.front().cost * q.front().kg;
q.pop_front();
}
q.push_back(array[i]);
}
while(!q.empty()){
//cout << q.front().kg << ' ' << q.front().cost << '\n';
sum += q.front().kg * q.front().cost;
q.pop_front();
}
fout << sum;
}
/*
element e;
e.kg = q.back().kg;
e.cost = array[i].cost;
e.sapt = -10000;
*/