Pagini recente » Cod sursa (job #3162236) | Cod sursa (job #1656567) | Cod sursa (job #2148425) | Cod sursa (job #2805621) | Cod sursa (job #437093)
Cod sursa(job #437093)
//Petre Andreea
#include <stdio.h>
#include <stdlib.h>
//structura gutuie :P
typedef struct gutui{
int g, h, l;
}gutui_t;
//partition de la quick_sort
int partition( gutui_t **a, int low, int high ){
int l, r;
gutui_t pivot, tmp;
pivot = (*a)[low];
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;
}
//quick-sort 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(){
//fisiere I\O
FILE *f,*out;
//variabile
int n, hmax, u, i, size = 0, val = 0;
int lev = 0;
gutui_t gutuie;
gutui_t *v;
int *ocupat;
f = fopen("gutui.in", "r");
out= fopen("gutui.out", "w");
fscanf(f,"%d %d %d\n",&n, &hmax, &u);
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;
}
}
//sortare rapida
quicksort(&v,0,size-1); //O(nlogn) in cazul mediu...in cel mai rau caz O(n^2)
//vector ce imi spune daca un nivel a fost ocupat deja sau nu
ocupat = (int *)calloc(hmax/u, sizeof(int)), val=0;
for(i = 0; i <size; i++) //O(n)
{
gutuie = v[i]; //O(1)
if( !ocupat[gutuie.l-1]){//O(1)
val += gutuie.g;
ocupat[gutuie.l-1] = 1;
}
else {
lev = gutuie.l; //O(1)
while(lev > 0 && ocupat[lev-1]==1 ) //O(hmax/u) in cel mai rau caz..deci un O(m)
lev--;
if(lev > 0 ){ //O(1)
ocupat[lev-1] = 1;
val+=gutuie.g;
}
}
}
fprintf(out, "%d", val);
free(ocupat);
free(v);
fclose(f);
fclose(out);
return 0;
}