Pagini recente » Cod sursa (job #2519985) | Cod sursa (job #91377) | Cod sursa (job #2545939) | Cod sursa (job #2657233) | Cod sursa (job #437110)
Cod sursa(job #437110)
#include <stdio.h>
#include <stdlib.h>
//structura gutuie :P
typedef struct gutui{
int g, h, l;
}gutui_t;
//partitionare quicksort
int partition( gutui_t **a, int low, int high ){
int l, r;
gutui_t pivot, tmp;
pivot.h = (*a)[low].h;
pivot.g = (*a)[low].g;
pivot.l = (*a)[low].l;
l = low;
r = high;
while ( l < r ) {
while( (*a)[l].g >= pivot.g) l++;
while( (*a)[r].g < pivot.g ) r--;
if ( l < r ) {
tmp = (*a)[l];
(*a)[l] = (*a)[r];
(*a)[r] = tmp;
}
}
(*a)[low] = (*a)[r];
(*a)[r] = pivot;
return r;
}
//quicksort recursiv
void quicksort( gutui_t **a, int low, int high ){
int pivot;
if ( high > low ){
pivot = partition( a, low, high );
quicksort( a, low, pivot-1 );
quicksort( a, pivot+1, high );
}
}
int main(){
FILE *f,*out;
int n, hmax, u, i, size = 0;
int lev = 0;
gutui_t gutuie;
f = fopen("gutui.in", "r");
out= fopen("gutui.out", "w");
//citire
fscanf(f,"%d %d %d\n",&n, &hmax, &u);
gutui_t *v = (gutui_t*)calloc(n, sizeof(gutui_t));
for (i = 0 ; i < n ;i ++){
fscanf(f, "%d %d\n", &gutuie.h, &gutuie.g);
if( gutuie.h <= hmax){
gutuie.l = (hmax - gutuie.h) / u + 1;
v[size++] = gutuie;
}
}
//ordonare dupa greutate
quicksort(&v,0,size-1);
int *ocupat = (int *)calloc(hmax/u, sizeof(int)), val=0;
//ocuparea nivelelor la care se ia gutuia
for(i = 0;i <size; i++)
{
gutuie = v[i];
if( !ocupat[gutuie.l-1]){
val += gutuie.g;
ocupat[gutuie.l-1] = 1;
}
else {
lev = gutuie.l;
while(lev > 0 && ocupat[lev-1]==1 )
lev--;
if(lev > 0 ){
ocupat[lev-1] = 1;
val+=gutuie.g;
}
}
}
fprintf(out, "%d", val);
fclose(f);
fclose(out);
return 0;
}