Cod sursa(job #2081149)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 4 decembrie 2017 08:54:55
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#define DIM 10005

using namespace std;

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

int N, X, L, current_dist, Wool;

int heap_count;

pair <int, int> H[DIM];

void up(int pos){

    int p, c;
    c = pos;
    p = pos / 2;

    while(p >= 1 && H[p].second < H[c].second){
        swap(H[p], H[c]);
        c = p;
        p /= 2;
    }

}

void down(int pos){

    int p, c;

    p = pos;
    c = 2 * pos;

    while(c <= heap_count){
        if(c + 1 <= heap_count && H[c + 1].second > H[c].second)
            c++;
        if(H[p].second < H[c].second){
            swap(H[p], H[c]);
            p = c;
            c *= 2;
        }
        else
            break;
    }

}

int main(){

    fin >> N >> X >> L;

    for(int i = 1; i <= N; i ++){
        int x, y;
        fin >> x >> y;
        H[ ++ heap_count ] = make_pair(x, y);
        up( heap_count );
    }

    current_dist = 0;

    while(heap_count){

        pair <int, int> Sheep = H[1];

        if(Sheep.first + current_dist <= X){
            Wool += Sheep.second;
            current_dist += L;
        }

        H[1] = H[ heap_count --];

        down(1);

    }

    fout << Wool << "\n";

}