Cod sursa(job #2784858)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 17 octombrie 2021 15:55:35
Problema Lupul Urias si Rau Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 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;
        oi[i].viata=(x-dist)/lung;

    }
    //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.size()==0)
        {
            break;
        }
        suma+=heap.top();
        heap.pop();
        cicluri--;
    }
    fout<<suma;
    return 0;
}