Cod sursa(job #767541)

Utilizator SteveStefan Eniceicu Steve Data 13 iulie 2012 19:21:29
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <queue>

using namespace std;

long long N, X, L;
priority_queue <pair <long long, long long>, vector <pair <long long, long long> >, greater <pair <long long, long long> > > hp;
priority_queue <pair <long long, long long>, vector <pair <long long, long long> >, greater <pair <long long, long long> > > lol;

void Citire () {
    long long a, b;
    ifstream fin ("lupu.in");
    fin >> N >> X >> L;
    for (long long i = 0; i < N; i++)
    {
        fin >> a >> b;
        a = (X - a) / L;
        hp.push (make_pair (-b, a));
    }
    fin.close ();
}

long long Business () {
    long long luate = 0, cnt = 0;
    while (1)
    {
        while (!hp.empty () && (hp.top ().second < 0 || hp.top ().second < luate)) hp.pop ();
        if (hp.empty ()) break;
        lol.push (make_pair (hp.top ().second, hp.top ().first));
        hp.pop ();
        while (!lol.empty () && luate + (long long) lol.size () > lol.top ().first)
        {
            cnt += -lol.top ().second;
            lol.pop ();
            luate++;
        }
    }
    return cnt;
}

void Scriere () {
    ofstream fout ("lupu.out");
    fout << Business ();
    fout.close ();
}

int main () {
    Citire ();
    Scriere ();
    return 0;
}