Cod sursa(job #993960)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 4 septembrie 2013 19:28:22
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

const int Nmax = 100005;

struct oaie
{
    int D;
    int A;

} v[Nmax];

struct cmp
{
    bool operator() ( const oaie &a, const oaie &b ) const
    {
        return a.D > b.D;
    }
};

struct comp
{
    bool operator() ( const oaie &a, const oaie &b ) const
    {
        return a.A < b.A;
    }
};

priority_queue < oaie, vector <oaie>, comp > MaxHeap;

int D, A;
int N, X, L;
uint64_t solution;

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

    f >> N >> X >> L;

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

        v[i].D = ( X - v[i].D ) / L + 1;
    }

    f.close();
}

void solve()
{
    int j = 1;

    for ( int i = v[1].D; i >= 1; i-- )
    {
        while ( v[j].D == i && j <= N )
        {
            MaxHeap.push( v[j] );
            j++;
        }

        while ( MaxHeap.top().D > X && !MaxHeap.empty() )
                    MaxHeap.pop();

        if ( !MaxHeap.empty() )
        {
            solution += MaxHeap.top().A;
            MaxHeap.pop();
        }
    }
}


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

    g << solution << "\n";

    g.close();
}

int main()
{
    read();
    sort( v + 1, v + N + 1, cmp() );
    solve();
    print();

    return 0;
}