Cod sursa(job #2820031)

Utilizator Luca_CristianZamfir Luca-Cristian Luca_Cristian Data 19 decembrie 2021 18:22:58
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb

#include <fstream>
#include <queue>

using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");


#define NMAX 100001

struct oaie
{
    int time, wool;
};
oaie oi[NMAX];


int aux, st1, i;
void swap_oi(oaie v[], int i, int j)
{
    aux = v[i].time;
    v[i].time = v[j].time;
    v[j].time = aux;

    aux = v[i].wool;
    v[i].wool = v[j].wool;
    v[j].wool = aux;

}

int part(oaie v[], int st, int dr)
{
    st1 = st - 1;
    for(i = st; i < dr; i++)
        if(v[i].time > v[dr].time)
        {
            st1++;
            swap_oi(v, st1, i);
        }
    st1++;
    swap_oi(v, st1, dr);
    return st1;
}

int qsort(oaie v[], int st, int dr)
{
    if(st < dr)
    {
        int piv = part(v, st, dr);
        qsort(v, st, piv - 1);
        qsort(v, piv + 1, dr);
    }
}

priority_queue <int> qwool;



int main()
{
    int n, i, dmax, d_pas, d_oaie, wool;

    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;
    }
    qsort(oi, 1, n);


    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 << "\n";

    return 0;
}