Cod sursa(job #2449808)

Utilizator victorv88Veltan Victor victorv88 Data 20 august 2019 19:32:06
Problema Lupul Urias si Rau Scor 68
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#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;
        if (oi[i].distanta<=d_max)
        {
            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 (long long i=nr_maxim; i>=1; --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();
        }
    }
    g << rez;

    return 0;
}