Cod sursa(job #993938)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 4 septembrie 2013 18:53:10
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

const int Nmax = 100005;

typedef pair<int,int> node;

int D[Nmax], A[Nmax];

struct cmp
{
    bool operator() ( const node &a, const node &b )
    {
        if ( a.first != b.first )
                return a.first < a.second;

        return a.second < b.second;
    }
};

priority_queue < node, vector <node>, cmp > MaxHeap;

int N, X, L;
int dist_max = 0, solution = 0;

void read()
{
    ifstream f("lupu.in");

    f >> N >> X >> L;

    for ( int i = 1; i <= N; ++i )
    {
            f >> D[i] >> A[i];

            if ( D[i] > X )
                    continue;

            MaxHeap.push( node( D[i], A[i] ) );
    }

    f.close();
}

void solve()
{
    while ( !MaxHeap.empty() )
    {
        while ( MaxHeap.top().first + dist_max > X && !MaxHeap.empty() )
                    MaxHeap.pop();

        if ( !MaxHeap.empty() )
        {
            solution += MaxHeap.top().second;
            dist_max += L;
            MaxHeap.pop();
        }
    }
}

void print()
{
    ofstream g("lupu.out");

    g << solution << "\n";

    g.close();
}

int main()
{
    read();
    solve();
    print();

    return 0;
}