Cod sursa(job #437733)
Utilizator | Data | 10 aprilie 2010 00:42:01 | |
---|---|---|---|
Problema | Gutui | Scor | 0 |
Compilator | cpp | Status | done |
Runda | teme_upb | Marime | 3.15 kb |
#include<stdio.h>
struct gutu {
int h;
int g;
};
gutu gutui[100];
void quickSort(gutu vect[], int stanga, int dreapta) {
int i = stanga, j = dreapta;
gutu tmp;
int pivot = vect[(stanga + dreapta) / 2].g;
while (i <= j) {
while (vect[i].g > pivot)
i++;
while (vect[j].g < pivot)
j--;
if (i <= j) {
tmp = vect[i];
vect[i] =vect[j];
vect[j] = tmp;
i++;
j--;
}
};
if (stanga < j)
quickSort(vect, stanga, j);
if (i < dreapta)
quickSort(vect, i, dreapta);
}
void quickSorth(gutu vect[], int stanga, int dreapta) {
int i = stanga, j = dreapta;
gutu tmp;
int pivot = vect[(stanga + dreapta) / 2].h;
while (i <= j) {
while (vect[i].h < pivot)
i++;
while (vect[j].h > pivot)
j--;
if (i <= j) {
tmp = vect[i];
vect[i] =vect[j];
vect[j] = tmp;
i++;
j--;
}
};
if (stanga < j)
quickSorth(vect, stanga, j);
if (i < dreapta)
quickSorth(vect, i, dreapta);
}
int main(){
FILE *f,*g;
int N, H, U, i, auxh,pondere[100],max=0,iaics[100],k,s,stanga;
f = fopen( "gutui.in", "r" );
g = 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 );
gutui[i].h=(H-auxh)/U+1;
if(gutui[i].h > max)
max=gutui[i].h;
fscanf ( f, "%d", &gutui[i].g );
}
quickSorth(gutui,0,N-1);
i=0;
int culese=0;
while(i<N-1){
stanga =i;
k=0;
while(gutui[i].h==gutui[i+1].h){
k++;
i++;
}
i++;
if(k!=0){
quickSort(gutui,stanga, stanga+k);
max--;
}
}
k=0;
for( i = 0; i < N; i ++){
if(k > max+1)
break;
else{
if( k < gutui[i].h) {
s=s+gutui[i].g;
k++;
}
} } ;
fprintf(g,"%d",s);
return 1;
}