Pagini recente » Cod sursa (job #2510604) | Cod sursa (job #420388) | Cod sursa (job #2622786) | Cod sursa (job #2559257) | Cod sursa (job #3125303)
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;
ifstream cin("lupu.in");
ofstream cout("lupu.out");
const int N=1e5;
struct oi
{
int d;
int a;
};
oi oaie[N+1];
long long sol;
int ratie;
priority_queue<int, vector<int>, greater<int>> pq;
bool comp(const oi& a, const oi& b)
{
return a.d < b.d;
}
int main()
{
int n, x, l;
cin >> n >> x >> l;
for(int i=1; i<=n; i++)
cin >> oaie[i].d >> oaie[i].a;
sort(oaie+1, oaie+1+n, comp); ///sortam oile dupa distanta fata de lup
for(int i=n; i>=1; i--)
{
if(oaie[i].d + ratie <=x) ///prindem intai oile cele mai departate (ele se vor departa mai curand cu l)
{
sol+=oaie[i].a;
ratie+=l;
pq.emplace(oaie[i].a);
}
else if(!pq.empty() && oaie[i].d + ratie - l <= x && oaie[i].a > pq.top())
{
///daca nu mai avem oi disponibile cautam o oaie mai putin departata cu mai multa lana
sol-=pq.top();
pq.pop();
pq.emplace(oaie[i].a);
sol+=oaie[i].a;
}
}
cout << sol;
return 0;
}