Cod sursa(job #848341)

Utilizator arrayAnghel Mihai array Data 5 ianuarie 2013 13:09:36
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
 
ifstream fin("lupu.in");
ofstream fout("lupu.out");
class cmp
{
public:
    inline bool operator()(const pair<long long, long long> &A, const pair<long long, long long> &B)
    {
        return A.first > B.first;
    }
    inline bool operator()(const long long &A, const long long &B)
    {
        return A < B;
    }
};
long long N, DMax, D, GG;
vector< pair<int, int> > A;
vector<int> H;
 
int main()
{
    fin >> N >> DMax >> D;
    A.resize(N + 1);
    for (long long i = 1; i <= N; ++i)
    {
        fin >> A[i].first >> A[i].second;
        if (A[i].first > DMax) A[i].first = 0;
        else A[i].first = (DMax - A[i].first) / D + 1;
    }
    sort(A.begin() + 1, A.end(), cmp());
    for (long long i = 1, step = A[1].first; i <= N && step; --step)
    {
        for (; step == A[i].first; H.push_back(A[i].second), push_heap(H.begin(), H.end(), cmp()), ++i);
        if (H.size()) GG += H.front(), pop_heap(H.begin(), H.end(), cmp()), H.pop_back();
    }
    fout << GG << '\n';
    fout.close();
    return 0;
}