Cod sursa(job #1982113)

Utilizator Firealex2Rotileanu Alexandru Firealex2 Data 17 mai 2017 18:30:11
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

ifstream fi("lupu.in");
ofstream fo("lupu.out");


int n,x,l;
priority_queue< pair<int, int> > lana; /// first distante (descresc), second inidce
int update, sol;

struct oaie{
    int dist, lana;
};

oaie O[100001];

void solve();

bool cmp(oaie a, oaie b)
{
    if(a.dist>b.dist)
        return true;
    return false;
}


int main()
{
    fi>>n>>x>>l;
    for(int i=1;i<=n;i++)
        fi>>O[i].dist>>O[i].lana;
    solve();
    cout<<sol;
    return 0;
}

void solve()
{
    sort(O+1,O+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(O[i].dist+update<=x)
            lana.push(make_pair(-O[i].lana,i)), update+=l;
        else if(O[i].dist<=x && -lana.top().first<O[i].lana)
        {
            lana.pop();
            lana.push(make_pair(-O[i].lana,i));
        }
    }

    while(!lana.empty())
        sol+=-lana.top().first,lana.pop();

    return;
}