Cod sursa(job #1556792)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 25 decembrie 2015 23:08:18
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

const int MAX_N = 100000;

class Sheep {
public:
    int x;
    int d;
    int w;

    bool operator <(const Sheep &other) const {
        return this->w < other.w;
    }
};

Sheep S[1 + MAX_N];
priority_queue < Sheep > Q;

bool sortSheep(Sheep A, Sheep B) {
    return A.d > B.d;
}

int main() {
    int n, x, l, i, j, k;
    long long totalWool = 0;

    in >> n >> x >> l;
    for(i = 1; i <= n; i++) {
        in >> S[i].x >> S[i].w;
        if(x < S[i].x) S[i].d = -1;
        else S[i].d = max(0, (x - S[i].x) / l);
    }

    sort(S+1, S+n+1, sortSheep);
    for(i = 1, S[++n] = Sheep{0, -1, 0}; i <= n; i++) {
        Q.push(S[i]);
        for(j = 1; j <= S[i].d - S[i+1].d && !Q.empty(); j++) {
            totalWool += Q.top().w;
            Q.pop();
        }
    }

    out << totalWool << '\n';
    return 0;
}