Cod sursa(job #437807)

Utilizator andra_serbanSerban Andra-Elena andra_serban Data 10 aprilie 2010 02:34:03
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 2.42 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 = lvl[i];
             lvl[i] = lvl[j];
             lvl[j] = t;

    }
    t = greutate[l];
    greutate[l] = greutate[j];
    greutate[j] = t;
    t = inaltime[l];
    inaltime[l] = inaltime[j];
    inaltime[j] = t;
    t = lvl[l];
    lvl[l] = lvl[j];
    lvl[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 );
     }

}

int find( int x, int v[], int nr ) {
    
    int i, k = 0;
    for( i = 1; i <= nr; i ++ )
         if( x == v[i] ) k ++;
    if( k != 0 ) return 1;      // returneaza 1 daca x apare in v
    return 0;                   // si 0, altfel
    
}

void gutui() {

    int i, j, suma = 0, nr = 0, k = 1, ok;
    
    for( i = 1; i <= N; i ++ ) 
         lvl[i] = ( H - inaltime[i] ) / U + 1 ;

    sort(1, N);
    
    for( i = N; i >= 1; i --) {
              ok = 0;
              for( j = lvl[i]; j >= 1; j -- )
                 if( ok != 1 && find(j, count, k) != 1) { 
                              count[k + 1] = j;
                              suma = suma + greutate[i];
                              ok = 1;
                              k = k + 1;
                   }
    }
    
    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();
    
}