Cod sursa(job #2027413)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 26 septembrie 2017 08:05:52
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <iostream>
#include <fstream>
#define DMAX 100009

using namespace std;

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

struct element{
    int dist;
    int lana;
}corespArb[DMAX];

int N, X, L;
int arb[DMAX], n;
int pozInArb[DMAX];
int n1;
int suma;

void inserareArb(int , int );
void validareSus(int );
void validareJos(int );

inline int tata(int k){
    return k / 2;
}

inline int fiuStanga(int k){
    return k * 2;
}

inline  int fiuDreapta(int k){
    return k * 2 + 1;
}

void citire(){
    in >> N >> X >> L;
    for(int i = 1; i <= N; i++){
        int a, b;
        in >> a >> b;
        if(a <= X){
            inserareArb(a, b);
        }
    }
}

void inserareArb(int dist, int lana){
    corespArb[++n1]. dist = dist;
    corespArb[n1].lana = lana;
    arb[++n] = n1;
    pozInArb[n1] = n;
    validareSus(n);
}

void validareSus(int k){
    while((k > 1) && corespArb[arb[k]].lana > corespArb[arb[tata(k)]].lana){
            swap(arb[k], arb[tata(k)]);
            swap(pozInArb[arb[k]], pozInArb[arb[tata(k)]]);
            k = tata(k);
    }
}

void stergere(int k){
    arb[k] = arb[n];
    n--;
    pozInArb[arb[n]] = k;
    validareJos(k);
}

void validareJos(int k){
    int fiu;
    do{
        fiu = 0;
        if(fiuStanga(k) <= n){
            fiu = fiuStanga(k);
            if((k <= n / 2) && corespArb[arb[fiu]].lana < corespArb[arb[fiuDreapta(k)]].lana){
                fiu = fiuDreapta(k);
            }
            if(corespArb[arb[k]].lana > corespArb[arb[fiu]].lana){
                fiu = 0;
            }
        }
        if(fiu != 0){
            swap(arb[k], arb[fiu]);
            swap(pozInArb[arb[k]], pozInArb[arb[fiu]]);
            k = fiu;
        }
    }while(fiu != 0);
}

void rezolvare(){
    int distantaActuala = 0;
    while(n > 0){
        if(corespArb[arb[1]].dist + distantaActuala > X){
            stergere(1);
        }else{
            suma += corespArb[arb[1]].lana;
            distantaActuala += L;
            stergere(1);
        }
    }
    out << suma;
}

int main() {
    citire();
    rezolvare();
    return 0;
}