Pagini recente » Cod sursa (job #988023) | Cod sursa (job #365421) | Cod sursa (job #355735) | Cod sursa (job #1000110) | Cod sursa (job #2288576)
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
struct oaie {
int dist, lana;
};
bool cmp(oaie o1, oaie o2) {
return o1.dist < o2.dist;
}
int main()
{
ifstream f("lupu.in");
ofstream g("lupu.out");
priority_queue<pair<int,int> > distanta;
int N, X, L;
f>>N>>X>>L;
int x,y;
oaie o;
vector<oaie> oi;
for (int i=0; i<N; i++) {
//f>>x>>y;
//distanta.push(make_pair(x,y));
f>>o.dist>>o.lana;
oi.push_back(o);
}
/*
for (int i=0; i<N; i++) {
pair<int,int> p;
p = distanta.top();
cout<<p.first<<' '<<p.second<<'\n';
distanta.pop();
}
*/
sort(oi.begin(), oi.end(), cmp);//sortate descrescator dupa distanta
int nr_maxim_alegeri;
nr_maxim_alegeri = X/L + 1;
int sum = 0, j = 0;
priority_queue<int> lana;
for (int i=nr_maxim_alegeri; i>=1; i--) {
//cout<<"intervalul curent: "<<X-i*L+1<<' '<<X-(i-1)*L<<'\n';
//cout << oi[j].dist << "\n";
while (X-i*L+1 <= oi[j].dist && oi[j].dist <= X-(i-1)*L && j<N) {
// cout << oi[j].lana << "\n";
lana.push(oi[j].lana);
j++;
}
if(!lana.empty()){
sum += lana.top();
//cout << "am ales" << lana.top() << "\n";
lana.pop();
}
}
g<<sum;
return 0;
}