Pagini recente » Borderou de evaluare (job #1681569) | Cod sursa (job #400864) | Borderou de evaluare (job #2013291) | Clasament wintership | Cod sursa (job #2809509)
#include <stdio.h>
#include <stdlib.h>
#define LMAX 100000
int heap[LMAX],hs,v[LMAX],ln[LMAX];
static inline int parent(int i) {return (i - 1) / 2;}
static inline int leftChild(int i) {return i * 2 + 1;}
static inline int rightChild(int i) {return i * 2 + 2;}
void quicksort(int begin, int end){
int b = begin, e = end, pivot = v[(begin + end)/2], aux;
while(v[b] > pivot)
b++;
while(v[e] < pivot)
e--;
while(b<e){
aux = v[b];
v[b] = v[e];
v[e] = aux;
aux = ln[b];
ln[b] = ln[e];
ln[e] = aux;
do{
b++;
} while(v[b] > pivot);
do{
e--;
} while(v[e] < pivot);
}
if(e > begin)
quicksort(begin, e);
if(e+1 < end)
quicksort(e+1, end);
}
void swap(int x, int y){
int aux = heap[y];
heap [y] = heap [x];
heap [x] = aux;
}
void climbHeap(int x){
if(x == 0)
return;
int p = parent(x);
if( heap[p] < heap[x] )
swap(x, p);
}
void downHeap(int x){
if(x >= hs)
return;
int st = leftChild(x), dr = leftChild(x), aux;
if(heap[st] == 0)
return;
if(heap[dr] != 0 && heap[dr] > heap[st]){
swap(dr,st);
aux = dr;
dr = st;
st = aux;
}
if(heap[st] > heap[x]){
swap(x, st);
downHeap(st);
}
}
void deleteMin(){
heap[0] = heap[hs-1];
hs--;
downHeap(0);
}
void add(int x){
heap[hs] = x;
hs++;
climbHeap(hs-1);
}
int main(){
int n,x,l,s,i,d;
FILE *fin, *fout;
fin = fopen("lupu.in","r");
fscanf(fin,"%d%d%d",&n,&x,&l);
for(i=0;i<n;i++){
fscanf(fin,"%d%d",&d,&ln[i]);
if(x >= d)
v[i] = (x-d) / l +1;
// printf("%d ",v[i]);
}
quicksort(0,n-1);
// for(i=0;i<n;i++)
// printf("%d ",v[i]);
// printf("\n");
// for(i=0;i<n;i++)
// printf("%d ",ln[i]);
// printf("\n");
i = 0;
s = 0;
// printf("\n",heap[0]);
while(i<n){
x = v[i];
while(i<n && v[i] == x){
add(ln[i]);
i++;
}
s+= heap[0];
// printf("%d ",heap[0]);
deleteMin();
}
fclose(fin);
fout = fopen("lupu.out","w");
fprintf(fout,"%d\n",s);
fclose(fout);
return 0;
}