Cod sursa(job #1149319)

Utilizator felixiPuscasu Felix felixi Data 21 martie 2014 17:47:53
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <algorithm>
#include <fstream>
#include <queue>

using namespace std;

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

const int NMAX = 100000;

struct OAIE{
    long long t,o;
};

OAIE v[NMAX+1];

bool comp_oaie( OAIE a, OAIE b ){
    if( a.t>b.t || (a.t==b.t && a.o>a.o) ) return 1;
    return 0;
}

struct comp{
    bool operator()(const OAIE &a, const OAIE &b) {
        return a.o <= b.o;
    }
};

long long N,X,L;

priority_queue<OAIE, vector<OAIE>, comp> Garden;

long long Tmax= -1;

void citire() {
    for( int i= 0;  i<N;  i++ ) {
        in >> v[i].t >> v[i].o;
        if( L != 0 ) {
            v[i].t= (X - v[i].t) / L+1;
            if( v[i].t > Tmax ) Tmax= v[i].t;
        }
    }
}

void Rezolva() {
    long long S= 0;
    for( int i= Tmax;  i>0;  i-- ) {
        int p= 0;
        while( v[p].t==i && p<N ) {
            Garden.push( v[p++] );
        }
        if( !Garden.empty() ) {
            S+= Garden.top().o;
            Garden.pop();
        }
    }
    out << S << '\n';
}


int main()
{
    in >> N >> X >> L;
    citire();
    sort( v, v+N, comp_oaie );
    Rezolva();
    return 0;
}