Cod sursa(job #2294244)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 2 decembrie 2018 02:42:38
Problema Lupul Urias si Rau Scor 76
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>

struct Data {
    Data (int Bound = 0, int Sum = 0) {
        this->Bound = Bound;
        this->Sum = Sum;
    }
    int Bound, Sum;
    bool operator < (const Data& Other) const {
        if (this->Bound == Other.Bound) return this->Sum < Other.Sum;
        return this->Bound < Other.Bound;
    }
};

int N, M, K;
int Head;
std::multiset <Data> Input;
std::priority_queue <int> Heap;

std::ifstream In("lupu.in");
std::ofstream Out("lupu.out");

void Citire() {
    In >> N >> M >> K;
    for (int i=0, x, y; i<N; ++i) {
        In >> x >> y;
        Input.insert(Data(x, y));
    }
}

void Rezolvare() {
    std::set <Data>::iterator it = Input.begin();
    long long Sum = 0;
    Data Top;

    for(Head = 0; Head <= M; Head += K) {
        while (it != Input.end() && it->Bound <= Head)
            Heap.push(it->Sum), ++it;
        if (!Heap.empty())
            Sum += 1LL*Heap.top(),
            Heap.pop();
    }   Out << Sum << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}