Cod sursa(job #2294396)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 2 decembrie 2018 13:02:58
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 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::vector <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.push_back(Data(x, y));
    }
}

void Rezolvare() {
    std::sort(Input.begin(), Input.end());

    long long Sum = 0;
    int Index = 0;
    Data Top;

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

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

    return 0;
}