Cod sursa(job #2291665)

Utilizator TooHappyMarchitan Teodor TooHappy Data 28 noiembrie 2018 14:42:59
Problema Lupul Urias si Rau Scor 84
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream in("lupu.in");
ofstream out("lupu.out");
 
int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);
    
    int n, x ,l; in >> n >> x >> l;
 
    vector< pair< int, int > > v(n);
    for(int i = 0; i < n; ++i) {
        in >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end());
 
    int idx = 0, r = x % l;
 
    priority_queue< int > pq;
    for(int i = 0; i < n; ++i) {
        if(v[i].first <= r) {
            pq.push(v[i].second);
            idx = i;
        } else {
            break;
        }
    }

    long long ans = 0;
    if(!pq.empty()) {
        ans += (pq.top() * 1LL);
        pq.pop();
    }
    
    r += l;
    for(int i = idx + 1; i < n; ++i) {
        if(v[i].first > x) {
            break;
        }

        if(v[i].first <= r) {
            pq.push(v[i].second);
        } else {
            if(!pq.empty()) {
                ans += (pq.top() * 1LL);
                pq.pop();
 
                r += l;
                --i;
            } else {
                r = v[i].first + (x - v[i].first) % l;
            }
        }
    }

    if(!pq.empty()) {
        ans += (pq.top() * 1LL);
        pq.pop();
    }
 
    out << ans << "\n";
 
    in.close(); out.close();
 
    return 0;
}