Cod sursa(job #1248689)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 25 octombrie 2014 20:09:14
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#define MAXN 100000
using namespace std;

struct sheep {
    int a, timp;
};

sheep v[MAXN + 1];
priority_queue <int> best;

bool comp(sheep x, sheep y) {
    return x.timp > y.timp;
};

int main () {
    ifstream cin("lupu.in");
    ofstream cout("lupu.out");
    
    int n, x, l;
    cin >> n >> x >> l;
    for (int i = 0 ; i < n ; ++i) {
        int d;
        cin >> d >> v[i].a;
        v[i].timp = ((x - d) / l) + 1;
    }

    sort(v, v + n, comp);

    int poz = 0, t = v[0].timp;
    int sol = 0;
    while (poz < n && t) {
        while (poz < n && v[poz].timp < t) {
           if (!best.empty()) {
               sol += best.top();
               best.pop();
           }
           --t;
        }

        if (poz < n) {
            int k = v[poz].timp;
            while (poz < n && v[poz].timp == k) {
                best.push(v[poz].a);
                ++poz;
            }
        }
    }

    while (t-- && !best.empty()) {
        sol += best.top();
        best.pop();
    }

    cout << sol;
    return 0;
}