Pagini recente » Profil Milanowskise9 | Profil smihail | Borderou de evaluare (job #3216848) | Cod sursa (job #216474) | Cod sursa (job #439270)
Cod sursa(job #439270)
#include<stdio.h>
// #include<conio.h>
int h[100000]; //inaltime
int g[100000]; //greutate
int oc[100000]; // are valori 0/1; daca prioritatea a fost data =1
void quickSortG(int vect[], int stanga, int dreapta) {
int i = stanga, j = dreapta;
int tmp1,tmp2;
int pivot = vect[stanga ];
while (i <= j) {
while ( vect[i] > pivot )
i ++;
while ( vect[j] < pivot )
j --;
if (i <= j) {
tmp1 = vect[i];
tmp2 = h[i];
vect[i] = vect[j];
h[i] = h[j];
vect[j] = tmp1;
h[j] = tmp2;
i ++;
j --;
}
};
if ( stanga < j )
quickSortG( vect, stanga, j);
if ( i < dreapta )
quickSortG( vect, i, dreapta );
}
int main(){
FILE *f,*f1;
int N, H, U, i, auxh, max=0,k, s=0;
f = fopen( "gutui.in", "r" );
f1 = fopen( "gutui.out", "w" );
fscanf(f, "%d", &N);
fscanf(f, "%d", &H);
fscanf(f, "%d", &U);
for( i = 0; i < N; i ++){
fscanf ( f, "%d", &auxh ); //citim ialtimea
h[i] = (H-auxh)/U+1; // pe ce nivel se afla gutuia
if(h[i] > max) //nivelul maxim
max=h[i];
fscanf ( f, "%d", &g[i] ); //citim greutatea
}
quickSortG(g,0,N-1); //sortam dupa greutate
int ind,j;
i=0;
while(i<N){ //parcurgem gutuile in ordinea greutatii,pana cand prioritatea ajunge 0
if(oc[h[i]]==0 ){
oc[h[i]]=1; //alocam prioritatea
s=s+g[i]; //gutuia este culeasa
}
else {
ind=h[i]; //vrem sa acordam prima prioritate disponibila
while(oc[ind]!=0 && ind>0 )
ind--; //prioritatea va fi mai mica decat cea gutui[i].h
if(ind>0){ //daca s-a gasit o prioritate disponibila, o alocam
oc[ind]=1;
s=s+g[i];
} //culegem gutuia
else break;
}
i++;
}
fprintf(f1,"%d",s);
// getch();
return 0;
}