Cod sursa(job #2150362)

Utilizator SenibelanMales Sebastian Senibelan Data 3 martie 2018 15:07:17
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

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

struct Sheep{
    int moment, wool;

    Sheep(int m, int w){
        moment = m;
        wool = w;
    }

    bool const operator<(const Sheep &other)const{
        return (wool < other.wool);
    }
};


const int NMAX = 100005;
int N, X, L;
int max_moment;
vector<Sheep> V;
priority_queue <Sheep> q;

bool cmp(Sheep a, Sheep b){
    return (a.moment > b.moment);
}

void Read(){
    in >> N >> X >> L;
    for(int i = 1; i <= N; ++i){
        int d, l;
        in >> d >> l;
        int moments = (X - d) / L + 1;
        if(d > X) moments = 0;
        max_moment = max(max_moment, moments);
        V.push_back(Sheep(moments, l));
    }
    sort(V.begin(), V.end(), cmp);
}

void SolveAndPrint(){
    int sum = 0;
    int index = 0;
    for(int i = max_moment; i >= 1; --i){
        for(; index < V.size(); ++index){
            if(V[index].moment == i)
                q.push(V[index]);
            else if(V[index].moment < i)
                break;
        }
        if(!q.empty()){
            sum += q.top().wool;
            q.pop();
        }
    }
    out << sum << "\n";
}


int main(){
    Read();
    SolveAndPrint();
    return 0;
}