Cod sursa(job #1586622)

Utilizator BrandonChris Luntraru Brandon Data 1 februarie 2016 15:02:43
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

struct sheep_property
{
    int dist, wool;
};

priority_queue <int> pq;

sheep_property sheep[100005];
int sheep_nr, wolf_radius, sheep_move, total_wool;

inline bool cmp(sheep_property a, sheep_property b) {
    return a.dist < b.dist;
}

void read() {
    cin >> sheep_nr >> wolf_radius >> sheep_move;
    for(int i = 1; i <= sheep_nr; ++i) {
        cin >> sheep[i].dist >> sheep[i].wool;
    }
}

void solve() {
    sort(&sheep[1], &sheep[sheep_nr] + 1, cmp);
    int j = 0;
    for(int i = 0; i <= wolf_radius; i += sheep_move) {
        for(; sheep[j].dist <= i; ++j) {
            pq.push(sheep[j].wool);
        }
        if(!pq.empty() ) {
            total_wool += pq.top();
            pq.pop();
        }
    }
}

void print() {
    cout << total_wool << '\n';
}

int main() {
    read();
    solve();
    print();
    return 0;
}