Cod sursa(job #2784864)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 17 octombrie 2021 16:02:50
Problema Lupul Urias si Rau Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

int n,x,lung;
long long int suma;

struct oaie
{
    int lana,viata;
} oi[100001];

priority_queue<int> heap;

bool cmp(oaie a,oaie b)
{
    if(a.viata==b.viata)
    {
        return a.lana>b.lana;
    }
    return a.viata>b.viata;
}

int main()
{
    fin>>n>>x>>lung;
    for(int i=1; i<=n; i++)
    {
        int dist,lana;
        fin>>dist>>lana;
        oi[i].lana=lana;
        if(lung!=0)
        {
            oi[i].viata=(x-dist)/lung;
        }
        else{
            oi[i].viata=x-dist;
        }


    }
    //sortez dupa durata de viata(durata in care poate fi atacata)
    sort(oi+1,oi+n+1,cmp);
    /*for(int i=1; i<=n; i++)
    {
        fout<<oi[i].lana<<" "<<oi[i].viata<<"\n";
    }*/

    int k=1,cicluri=oi[1].viata;

    while(cicluri>=0)
    {
        int nivel=oi[k].viata;
        while(k<=n && oi[k].viata==nivel)
        {
            heap.push(oi[k].lana);
            k++;
        }
        if(!heap.empty())
        {
            suma+=heap.top();
            heap.pop();

        }
        cicluri--;
    }
    fout<<suma;
    return 0;
}