Cod sursa(job #2183447)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 23 martie 2018 10:22:36
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 100 * 1000 + 10;

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

map<int, vector<int>, greater<int>> pe_timp
    {greater<int>()};

int n, x, l;

int main(){
    f >> n >> x >> l;

    for(int i = 0, poz, val; i < n; ++i){
        f >> poz >> val;
        const int timp =
            (x - poz) / l;
        pe_timp[timp].push_back(val); }
    pe_timp[-1].push_back(0);

    priority_queue<int> blana;
    int cur_timp = (1ll<<31) - 1;
    long long sol = 0;
    while(cur_timp >= 0){
        if(pe_timp.find(cur_timp) != end(pe_timp))
            for(auto& x : pe_timp[cur_timp])
                blana.push(x);
        if(!blana.empty()){
            sol += blana.top();
            blana.pop(); }
        cur_timp--;
        if(blana.empty())
            cur_timp = pe_timp.lower_bound(cur_timp)
                ->first;
    }
    g << sol << endl;
    return 0;
}