Cod sursa(job #1239974)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 10 octombrie 2014 08:57:03
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<queue>
#include<algorithm>

using namespace std;

ifstream fin( "lupu.in" );
ofstream fout( "lupu.out" );

typedef long long i64;

const int nmax = 100000;

struct oaie{ i64 d, a; } v[ nmax + 1 ];
bool cmp( oaie x, oaie y ) {
    return ( x.d < y.d );
}
priority_queue <i64> h;

int main() {
    i64 n, l, x, sol, ii;
    fin >> n >> x >> l;
    for( int i = 0; i < n; ++ i ) {
        fin >> v[ i ].d >> v[ i ].a;
        v[ i ].d = ( x - v[ i ].d ) / l + 1; // numarul de ture a.i. oaia i e ok
    }
    sort( v, v + n, cmp );

    sol = 0; ii = n - 1;
    for( int t = v[ ii ].d; t > 0; -- t ) {
        while ( ii > 0 && v[ ii ].d == t ) {
            h.push( v[ ii ].a );
            -- ii;
        }

        if ( !h.empty() ) {
            sol += h.top();
            h.pop();
        } else if ( ii > 0 ) {
            t = v[ ii ].d + 1;
        }
    }

    fout << sol << '\n';

    fin.close();
    fout.close();
    return 0;
}