Cod sursa(job #438133)

Utilizator andra_serbanSerban Andra-Elena andra_serban Data 10 aprilie 2010 15:16:36
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 4.21 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;
}

/* int partition2(int l, int r) {
    
    int pivot, i, j, t;
    pivot = ( H - inaltime[i] ) / U + 1; 
    i = l;
    j = r + 1;
    
    while(1) {
             do i ++; while( ( H - inaltime[i] ) / U + 1 <= pivot && i <= r );
             do j --; while( ( H - inaltime[i] ) / U + 1 > 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 );
     }

}
/*
void sort2( int l, int r ) {
     
     int j;
     
     if( l < r ) {
         j = partition( l, r );
         sort2( l, j - 1);
         sort2( 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, nivel, max = 0;
    
    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(max > 0) {
              nivel = ( H - inaltime[i] ) / U + 1;
              if(nivel == count[nivel] ) { 
                              suma = suma + greutate[i];
                              while( nivel < max ) {
                                 count[nivel] = count[nivel + 1];
                                 nivel = nivel + 1;
                              }
                              max = max - 1;
              }
              else {
                   suma = suma + greutate[ i ];
                   while( nivel < max ) {
                      count[nivel - ( N - i )] = count[nivel - ( N - i ) + 1];
                      nivel = nivel + 1;
                   }
                   max = max - 1;
              }
              }
                   
    }
    
/*    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();
    
}