Cod sursa(job #1922010)

Utilizator RaresEGaySopterean Adrian RaresEGay Data 10 martie 2017 15:41:15
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <algorithm>

#define INF 0x3f3f3f3f
#define maxn 100050

using namespace std;

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

priority_queue <int> pq;

int n, d, l, k;
long long sol;
int tmaxim = -INF;

struct oi{
    int tmax, dist, lana;
}v[maxn];

inline int compare(oi A, oi B){
    return (A.tmax < B.tmax);
}

int main (){
    f >> n >> d >> l;
    for(int i = 1; i <= n; ++i){
        f >> v[i].dist >> v[i].lana;
        v[i].tmax = (d - v[i].dist) / l + 1;
        tmaxim = max(tmaxim, v[i].tmax);
    }

    sort(v + 1, v + n + 1, compare);
    k = n;
    for(int i = tmaxim; i >= 1; --i){
        for(int j = k; j >= 1; --j){
            if(v[j].tmax == i){
                pq.push(v[j].lana);
                --k;
            }
            else break;
        }
        sol += pq.top();
        pq.pop();
    }
    g << sol << '\n';
}