Cod sursa(job #1894291)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 26 februarie 2017 18:36:27
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

const int NMax = 100000 + 5;

int N,X,L;
long long sol;
priority_queue<int> h;

struct elem {
    int dist,val;
}v[NMax];
// v - vector initial
// h - heap care, pentru un anumit moment, retine oaie cu valoare maxima de lana dintre cele introduse

bool cmp (elem a,elem b) {
    return a.dist<b.dist;
}

int main() {
    in>>N>>X>>L;

    for (int i=1;i<=N;++i) {
        in>>v[i].dist>>v[i].val;
    }

    // se ordoneaza crescator dupa distanta fata de lup
    sort(v+1,v+N+1,cmp);

    int minDist = v[1].dist;
    if (minDist > X) {
        cout<<0;
        return 0;
    }

    int rem = X/L;
    int addedDistance = rem*L;

    // in loc sa se incerce luarea cate unei oi de la inceput
    // se incearca luarea cate unei oi in ordine inversa
    // de la ultima oaie care s-ar putea lua
    int i = 1;
    while (0<=addedDistance) {
        // se adauga noile oi
        while (i<=N && (v[i].dist + addedDistance <= X)) {
            h.push(v[i++].val);
        }

        if (!h.empty()) {
            sol += h.top();
            h.pop();
        }

        addedDistance -= L;
    }

    out<<sol;
    return 0;
}