Cod sursa(job #1414817)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 3 aprilie 2015 02:55:16
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAXN 100050
 
int N, X, L;
int A[MAXN];
int B[MAXN];
int C[MAXN];
priority_queue<int, vector<int>, greater<int> > S;
 
bool cmp(int a, int b) {
    if (A[a] != A[b]) {
        return A[a] < A[b];
    }
    return B[a] < B[b];
}
 
int main() {
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out","w", stdout);
     
    scanf("%d %d %d", &N, &X, &L);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &A[i], &B[i]);
        C[i] = i;
    }
    sort(C, C + N, cmp);
     
    int i = N - 1;
    while (i >= 0) {
        if (A[ C[i] ] > X) {
			i--;
            continue;
        }
        int d = (X - A[ C[i] ]) / L + 1;
        while (i >= 0 && (X - A[ C[i] ]) / L + 1 == d) {
            S.push(B[ C[i] ]);
            i--;
        }
         
        while (S.size() > d) {
            S.pop();
        }
    }
     
    long long ans = 0;
    while (!S.empty()) {
        ans += S.top();
        S.pop();
    }
     
    printf("%lld\n", ans);
     
    return 0;
}