Cod sursa(job #2273691)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 31 octombrie 2018 20:45:19
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

#define d first
#define ct second

pair<int, int> oi[MAXN];
priority_queue<int> heap;

int main()
{
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");
    int n, x, l;
    fin >> n >> x >> l;
    for(int i = 1; i <= n; ++i){
        fin >> oi[i].d >> oi[i].ct;
        oi[i].d = (x - oi[i].d) / l;
    }
    sort(oi + 1, oi + n + 1);
    long long tot = 0;
    int pos = n;
    x /= l;
    while(x >= 0){
        while(pos > 0 && oi[pos].d >= x){
            heap.push(oi[pos].ct);
            pos--;
        }
        if(!heap.empty()){
            tot += heap.top();
            heap.pop();
        }
        x--;
    }
    fout << tot;
    return 0;
}