Cod sursa(job #1149321)

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

using namespace std;

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

const int NMAX = 100000;

struct OAIE{
    int t,m;
};

OAIE v[NMAX+1];

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

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

int N,X,L;

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

long long Tmax= -1;
int p= 0;

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


int main()
{
    in >> N >> X >> L;
    for( int i= 0;  i<N;  i++ ) {
        in >> v[i].t >> v[i].m;
        if( L != 0 ) {
            v[i].t= (X - v[i].t) / L + 1;
            if( v[i].t > Tmax ) Tmax= v[i].t;
        }
    }
    sort( v, v+N, comp_oaie );
    Rezolva();
    return 0;
}