Pagini recente » Cod sursa (job #233039) | Cod sursa (job #1248636) | Cod sursa (job #2498040) | Cod sursa (job #451726) | Cod sursa (job #2027413)
#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;
}