Cod sursa(job #311748)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 4 mai 2009 00:56:11
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct oaie {
    int d,l;

    oaie(int x, int y) {
        d = x; l = y;
    }

    bool operator<(const oaie &a) const {
        return d<a.d;
    }
};


int main() {
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");

    int n,t,l,x,y;

    fin>>n>>t>>l;

    vector<oaie> V;

    while(n--) {
        fin>>x>>y;
        V.push_back(oaie((t-x)/l +1 , y));
    }
    sort(V.begin(), V.end());

    long long rez=0;

    priority_queue<int> Q;

    for (int t = V.back().d,m=0; t && !V.empty(); t = m) {
        while(!V.empty() && V.back().d == t) {
            Q.push(V.back().l);
            V.pop_back();
        }
        m = V.empty() ? 0 : V.back().d;
        while(!Q.empty() && t>m) {
            rez += Q.top();
            Q.pop();
            t--;
        }
    }

    fout<<rez<<endl;

    fin.close();
    fout.close();
    return 0;
}