Cod sursa(job #437743)

Utilizator andreea03_07Andreea Oprisan andreea03_07 Data 10 aprilie 2010 00:56:25
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.33 kb
#include <stdio.h>
#include <stdlib.h>


void quickSort (int a[],int b[], int lo, int hi) {

    int i=lo, j=hi, h;
    int x=a[(lo+hi)/2];

    do
    {    
        while (a[i]>x) i++; 
        while (a[j]<x) 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--;
        }
    } while (i<=j);

    if (lo<j) quickSort(a,b, lo, j);
    if (i<hi) quickSort(a,b, i, hi);
}

int main() {
    int N, H, U, h[100000],g[100000],i,s=0,j,n,aux,p[100000],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);
    
          
    p[0] = (H - h[0])/U +1;
    m[(H - h[0])/U +1] = 1;
    for ( i = 1; i < N; i++){
        x = (H - h[i])/U +1;
        max = 0;
        for ( j = x; j > 0; j--)
            if (m[j] != 0 ) break; 
               else if (j >max) max = j;
        p[i]=max;
        m[max]=1;
    }
    
    for ( i = 0; i < N; i++) 
         if (p[i] > 0) s=s+g[i];
        
    
    fprintf(f2,"%d",s); 
    fclose(f1);
    fclose(f2);
    
}