Cod sursa(job #2823853)

Utilizator Luca_CristianZamfir Luca-Cristian Luca_Cristian Data 29 decembrie 2021 21:50:45
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <algorithm>
#include <fstream>
#include <queue>

using namespace std;


#define NMAX 100005


priority_queue <int> qwool;


struct oaie{
    int wool, time;
    bool operator < (const oaie &o) {
        return o.time < time;
    }
};
oaie oi[NMAX];



ifstream fin("lupu.in");
ofstream fout("lupu.out");
int main()
{
    int n, i, dmax, d_pas, d_oaie;

    fin >> n >> dmax >> d_pas;

    for(i = 1; i <= n; i++)
    {
        fin >> d_oaie >> oi[i].wool;
        oi[i].time = (dmax - d_oaie) / d_pas;
    }
    sort(oi + 1, oi + n + 1);

    int time = oi[1].time;
    long long rez = 0;
    i = 1;
    while(time >= 0)
    {
        while(i <= n && oi[i].time >= time)
        {
            qwool.push(oi[i].wool);
            i++;
        }

        if(!qwool.empty())
        {
           rez += qwool.top();
           qwool.pop();
        }

        time--;
    }
    fout << rez;

    return 0;
}