Pagini recente » Cod sursa (job #1300773) | Cod sursa (job #2385681) | Cod sursa (job #499756) | Cod sursa (job #37240) | Cod sursa (job #439585)
Cod sursa(job #439585)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int N,H,U;
typedef struct {
int h,g;
} gutuie;
gutuie *gutui;
FILE *f,*g;
bool comp(gutuie c1, gutuie c2) {
return c1.h > c2.h;
return true;
}
bool compheap(int c1, int c2){
return c1 > c2;
}
int main(){
int i,k,hc,j;
int max = 0;
int M;
int *heap;
f = fopen("gutui.in","r");
g = fopen("gutui.out","w");
fscanf(f,"%d %d %d\n",&N,&H,&U);
gutui = (gutuie*)calloc(N,sizeof(gutuie));
for(i=0;i<N;i++)
fscanf(f,"%d %d\n",&gutui[i].h,&gutui[i].g);
//afisare();
sort(gutui,gutui+N,comp);
//afisare();
//se elimina gutuile care sunt la inaltimi mai mari de H
k=0;
while(gutui[k].h>H)
k++;
for(i=0;i<N-k;i++)
gutui[i]=gutui[i+k];
N=N-k;
//afisare();
k = 0;
hc = H;
i = 0;
while(i<N){
while(gutui[i].h<=hc && gutui[i].h>(hc-U) && i<N){
gutui[i].h = k;
i++;
}
hc = hc - U;
k++;
}
M = k ;
if(N<M) M = N;
heap = (int*)calloc(N,sizeof(int));
i = 0;
j= 0;
k = 0;
while(j<N){
if(gutui[j].h!=i){
i = gutui[j].h;
}
if(k<=i){
heap[k] = gutui[j].g;
k++;
push_heap(heap,heap+k,compheap);
}
else{
if(heap[0]<gutui[j].g){
pop_heap(heap,heap+k,compheap);
heap[k-1] = gutui[j].g;
push_heap(heap,heap+k,compheap);
}
}
j++;
}
for(i=0;i<k;i++)
max = max + heap[i];
fprintf(g,"%d\n",max);
fclose(f);
fclose(g);
return 0;
}