Cod sursa(job #438865)

Utilizator andreea03_07Andreea Oprisan andreea03_07 Data 11 aprilie 2010 01:54:13
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.1 kb
#include <stdio.h>
#include <stdlib.h>

//sortare quickSort dupa un vector a
void quickSort (int a[],int b[], int l, int r) {
    int i = l, j = r, aux, m;
    m = a[( l + r ) / 2];
    while (i <= j) {    
        while ( a[i] > m ) 
              i++; 
        while ( a[j] < m ) 
              j--;
        if ( i <= j ) {
            aux = a[i]; a[i] = a[j]; a[j] = aux;
            aux = b[i]; b[i] = b[j]; b[j] = aux;
            i++; j--;
        }
    }
    if ( l < j ) 
         quickSort(a, b, l, j);
    if ( i < r ) 
         quickSort(a, b, i, r);
}

int main() {
    int N, H, U, h[100000], g[100000], i, s = 0, j, m[100000], x, max;
    FILE *f1, *f2;
    f1 = fopen ("gutui.in", "r");
    f2 = fopen ("gutui.out", "w");
    fscanf(f1, "%d", &N);
    fscanf(f1, "%d", &H);
    fscanf(f1, "%d", &U);
    for ( i = 0; i < N; i++) {
        fscanf(f1, "%d", &h[i]);
        fscanf(f1, "%d", &g[i]);
    }
    
    //sortare dupa greutate
    quickSort(g, h, 0, N);
    
    //m este un vector care poate lua valoarea 0 sau 1
    //1 - daca indicele lui m este un pas luat de o inaltime
    //0 - daca indicele lui m este un pas disponibil
    m[( H - h[0] ) / U + 1] = 1;     
    s = g[0];
    
    for ( i = 1; i < N; i++){
        x = ( H - h[i] ) / U + 1;       // pasul la care poate culege gutuia cel mai tarziu
        max = 0;
        for ( j = x; j > 0; j--)        // se verifica daca pasul respectiv este ocupat de alta inaltime 
            if ( m[j] == 0 )            // daca da inaltimii corespunzatoare i se atribuie cel mai mare pas mai mic 
               if ( j > max )           //       decat el disponibil
                  max = j;
        if ( max > 0 )                  // daca gutuia de la inaltimea h[i] poate fi culeasa la un anumit pas, greutatea
            s = s + g[i];               //       ei se adauga la suma totala   
        m[max] = 1;                     // pasul atribuit inaltimii este marcat cu 1, deci devine nedisponibil  
    }
    
    fprintf(f2, "%d", s); 
    fclose(f1);
    fclose(f2);
    
    return 0;
    
}