Pagini recente » Cod sursa (job #1390570) | Cod sursa (job #2441156) | Cod sursa (job #1556734) | Cod sursa (job #1949026) | Cod sursa (job #2449791)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
long long n, d_max, ratie, nr_maxim, rez;
struct o
{
long long distanta, lana;
} oi[100005];
class comparare_distanta
{
public:
bool operator() (o& oaie1, o& oaie2)
{
return oaie1.distanta>oaie2.distanta;
}
};
class comparare_lana
{
public:
bool operator() (o& oaie1, o& oaie2)
{
return oaie1.lana<oaie2.lana;
}
};
priority_queue<o,vector<o>,comparare_distanta>queue_distanta;
priority_queue<o,vector<o>,comparare_lana>queue_lana;
int main()
{
f >> n >> d_max >> ratie;
for (int i=1; i<=n; ++i)
{
f >> oi[i].distanta >> oi[i].lana;
oi[i].distanta=(d_max-oi[i].distanta)/2+1;
if (oi[i].distanta>nr_maxim)
nr_maxim=oi[i].distanta;
queue_distanta.push(oi[i]);
}
for (int i=1; i<=nr_maxim; ++i)
{
while (!queue_distanta.empty() && queue_distanta.top().distanta == i)
{
queue_lana.push(queue_distanta.top());
queue_distanta.pop();
}
if (!queue_lana.empty())
{
rez+=queue_lana.top().lana;
queue_lana.pop();
while(!queue_lana.empty() && queue_lana.top().distanta<=i)
queue_lana.pop();
}
}
g << rez;
return 0;
}