Cod sursa(job #437770)

Utilizator andreea03_07Andreea Oprisan andreea03_07 Data 10 aprilie 2010 01:34:17
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.19 kb
#include <stdio.h>

#include <stdlib.h>


void quickSort (int a[],int b[], int l, int r) {
  
    int i=l, j=r, h, m;
    m=a[(l+r)/2];
    while (i<=j) {    
        while (a[i]>m) i++; 
        while (a[j]<m) j--;
        if (i<=j) {
            h=a[i]; a[i]=a[j]; a[j]=h;
            h=b[i]; b[i]=b[j]; b[j]=h;
            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,n,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]);
    }
    
    quickSort(g,h,0,N);
    
    m[(H - h[0])/U +1] = 1;
    s=g[0];
    for ( i = 1; i < N; i++){
        x = (H - h[i])/U +1;
        max = 0;
        for ( j = x; j > 0; j--)
            if (m[j] == 0 ) 
               if (j >max) max = j;
        if (max > 0) s=s+g[i];
        m[max]=1;
    }
    
        
    
    fprintf(f2,"%d",s); 
    fclose(f1);
    fclose(f2);
    
}