Cod sursa(job #977837)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 26 iulie 2013 20:13:15
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>

using namespace std;

ifstream cin("lupu.in");
ofstream cout("lupu.out");

const int MAXN = 100005;
const int oo = (1<<31)-1;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

Graph G;
int N, X, L, M, D, A, Dist;
long long Answer;
priority_queue <int> MaxHeap;

int main() {
    cin >> N >> X >> L;
    for(int i = 1 ; i <= N ; ++ i) {
        cin >> D >> A;
        Dist = (X - D)/L + 1;
        M = max(M, Dist);
        if(Dist >= 0){
            G[Dist].push_back(A);
        }
    }
    cin.close();
    for(int i = M ; i ; -- i) {
        for(It it = G[i].begin(), fin = G[i].end() ; it != fin ; ++ it)
            MaxHeap.push(*it);
        if(!MaxHeap.empty())
            Answer += MaxHeap.top(), MaxHeap.pop();
    }
    cout << Answer << "\n";
    cout.close();
    return 0;
}