Cod sursa(job #2465290)

Utilizator Savu_Stefan_CatalinSavu Stefan Catalin Savu_Stefan_Catalin Data 29 septembrie 2019 19:08:13
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
struct nya{int st,dr;};
nya a[100001];
int nr,nr1,s,n,x,l,i,j,op;
long long rez;
priority_queue <int> Q;
int cmp(nya a,nya b)
{
    return make_pair(a.st, a.dr) > make_pair(b.st, b.dr);
}
int main()
{
    in>>n>>x>>l;
    for (i=1;i<=n;++i)
    {
        in>>a[i].st>>a[i].dr;
        if(x < a[i].st)
            a[i].st = a[i].dr = 0;
        else
            a[i].st=(x-a[i].st)/l+1;
    }
    // adaugam o oaie "nula":
    n++;

    int last_poz = 0;
    sort(a+1,a+n+1,cmp);
    for (i=1;i<=n;)
    {
        int curr_poz = a[i].st;
        for(int j = curr_poz + 1; j <= last_poz && !Q.empty(); ++j){
            rez += Q.top();
            Q.pop();
        }

        for( ; i <= n && a[i].st == curr_poz; ++i)
            Q.push(a[i].dr);
      last_poz=curr_poz;
    }
    out<<rez;
    return 0;
}