Cod sursa(job #1152499)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 24 martie 2014 19:25:51
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <algorithm>
#include <queue>
#define MAXN 100001
using namespace std;

struct oy {
    int d, a, time;
};

oy v[MAXN];

bool sortare( oy x, oy y ) {
    return x.time > y.time;
}

priority_queue <int> PQ;

int main () {
    FILE *f, *g;
    f = fopen( "lupu.in", "r" );
    g = fopen( "lupu.out", "w" );

    int n, x, l, key;
    long long sol = 0;

    fscanf( f, "%d%d%d", &n, &x, &l );

    for( int i = 0 ; i < n ; ++i ) {
        fscanf( f, "%d%d", &v[i].d, &v[i].a );
        v[i].time = ( x - v[i].d ) / l + 1;
        if( v[i].d > x )
            v[i].time = 0;
    }

    sort( v, v + n, sortare );

    int poz = 0;
    while( poz < n && v[poz].time > 0 ) {
        key = v[poz].time;
        while( poz < n && v[poz].time == key ) {
            PQ.push(v[poz].a);
            ++poz;
        }
        sol += PQ.top();
        PQ.pop();
    }

    fprintf( g, "%lld\n", sol );

    fclose( f );
    fclose( g );

    return 0;
}