Pagini recente » Cod sursa (job #2783042) | Cod sursa (job #2291428) | Cod sursa (job #1759893) | Cod sursa (job #2395897) | Cod sursa (job #3220847)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream in ("lupu.in");
ofstream out ("lupu.out");
struct oaie
{
int dist, wool, section;
};
#define MAX_N 100000
oaie v[MAX_N];
priority_queue<int> heap;
bool cmp (oaie a, oaie b)
{
if(a.section == b.section)
return a.wool > b.wool;
return a.section < b.section;
}
int extractTop() {
int top;
top = 0;
if (!heap.empty()) {
top = heap.top();
heap.pop();
}
return top;
}
int main()
{
int n, x, l;
in >> n >> x >> l;
for(int i = 0; i < n; ++i)
{
in >> v[i].dist >> v[i].wool;
v[i].section = ( x - v[i].dist ) / l + 1;
if(v[i].section < 0) v[i].section = -1;
}
sort(v, v + n, cmp);
int curr = v[0].section, no = 0, nr = 0, ans = 0;
for(int i = 0; i < n; ++i)
{
if(v[i].section != curr)
{
curr++;
no = 0;
}
//cout << v[i].wool << " " << v[i].section << " | " << no << " " << curr << " " << nr << " " << ans << '\n';
if(no <= curr - nr)
{
//this can enter
nr++;
no++;
ans += v[i].wool;
heap.push(v[i].wool);
} else if(no < curr)
{
no++;
int top = extractTop();
if(v[i].wool > top)
{
ans += v[i].wool - top;
heap.push(v[i].wool);
}
}
}
out << ans;
return 0;
}