Cod sursa(job #993928)

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

using namespace std;

const int Nmax = 100005;

typedef pair<int,int> node;

int D[Nmax], A[Nmax];

priority_queue < node, vector <node> > 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];

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

    f.close();
}

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

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

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

    g << solution << "\n";

    g.close();
}

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

    return 0;
}