Cod sursa(job #438337)

Utilizator andra_serbanSerban Andra-Elena andra_serban Data 10 aprilie 2010 17:58:01
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 2.64 kb
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
//#include<conio.h>

int n;
int N;
int H;
int U;
int count[100003];

int lvl[100003];
int inaltime[100003];
int greutate[100003];

void write(int x) {

    FILE * g = fopen("gutui.out", "w");

    fprintf(g, "%d", x);

}

int partition(int l, int r) {
    
    int pivot, i, j, t;
    pivot = greutate[l];
    i = l;
    j = r + 1;
    
    while(1) {
             do i ++; while( greutate[i] <= pivot && i <= r );
             do j --; while( greutate[j] > pivot );
             if( i >= j ) break;
             t = greutate[i];
             greutate[i] = greutate[j];
             greutate[j] = t;
             t = inaltime[i];
             inaltime[i] = inaltime[j];
             inaltime[j] = t;

    }
    t = greutate[l];
    greutate[l] = greutate[j];
    greutate[j] = t;
    t = inaltime[l];
    inaltime[l] = inaltime[j];
    inaltime[j] = t;
    return j;
}

void sort( int l, int r ) {
     
     int j;
     
     if( l < r ) {
         j = partition( l, r );
         sort( l, j - 1);
         sort( j + 1, r );
     }

}

void gutui() {

    int i, suma = 0, nivel, max = 0;
    int j;
    
    for( i = 1; i <= N; i ++ ) 
         if( (H - inaltime[i]) / U + 1 > max ) max = (H - inaltime[i]) / U + 1;
         
    for( i = 1; i <= max; i ++ ) 
         count[i] = i;

    sort(1, N);
    
    for( i = N; i >= 1; i --) {
         if(count[1]>0) {
              nivel = ( H - inaltime[i] ) / U + 1;
              //if(nivel == count[nivel] ) { 
                              suma = suma + greutate[i];
                              for( j = nivel - N + i; j <= max - 1; j ++ ) 
                                 count[j] = count[j + 1];
                              count[max] = 0;
              //}
            /*  else {
                   suma = suma + greutate[ i ];
                   for( j = nivel - N + i - 1; j <= max - 1; j ++ )  {
                      count[j] = count[j + 1];
                   }
                   count[max] = 0;
              } */
         }          
    }
    
/*    for (i = 1; i <= N; i++) {
        printf("%d ", inaltime[i]);
        printf("%d",  greutate[i]);
        printf("\n");
    } 
    printf("%d ", suma);
*/    
    write(suma);
}


int main() {
 
    FILE * f = fopen("gutui.in", "r");
    int i;

    fscanf(f, "%d", &N);
    fscanf(f, "%d", &H);
    fscanf(f, "%d", &U);

    for (i = 1; i <= N; i++) {
        fscanf(f, "%d", &inaltime[i]);
        fscanf(f, "%d", &greutate[i]);
    } 
    
    gutui();
    
    return 0; 
//   getch();
    
}