Cod sursa(job #2287012)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 21 noiembrie 2018 12:07:06
Problema Lupul Urias si Rau Scor 64
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define ll long long
#define PII pair < int , int >
#define MOD 1000000007
 
using namespace std;
 
ll n, m, l;

struct my {
    int pos, val, en;
};

my a[100100];

ll rs;
multiset < ll > S;
vector < int > V;
unordered_map < int , vector < int > > M;
unordered_map < int, bool > N;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    ifstream cin("lupu.in");
    ofstream cout("lupu.out");
 
    cin >> n >> m >> l;

    ll r = (m + 1) % l;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].pos >> a[i].val;

        if (a[i].pos < r) S.insert(a[i].val);
        else {
            if (!N[(a[i].pos - r) / l]) {
                N[(a[i].pos - r) / l] = 1;
                V.push_back((a[i].pos - r) / l);
            }

            M[(a[i].pos - r) / l].push_back(a[i].val);
        }
    }

    sort(V.begin(), V.end());

    if (S.size()) rs += *S.rbegin(), S.erase(S.find(*S.rbegin()));

    int last = -1;
    for (auto it : V) {
        for (auto it2: M[it]) {
            S.insert(it2);
        }

        int cp = it;
        // cout << cp << " " << last << "\n";
        while (S.size() && cp - last >= 1) rs += *S.rbegin(), S.erase(S.find(*S.rbegin())), cp--;

        last = it;
    }

    cout << rs;
    return 0;
}