Cod sursa(job #429353)

Utilizator points_hunterAdrian Dobrescu points_hunter Data 30 martie 2010 01:22:03
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.12 kb
#include<stdio.h>

int i, N, H, U, G;
int h[100000], g[100000];

void swap(int i, int j){
     int aux = h[i];
     h[i] = h[j];
     h[j] = aux;
     aux = g[i];
     g[i] = g[j];
     g[j] = aux;
}

int partitie(int left, int right){
    int i, j, x = h[left];
    i = left;
    for(j = left + 1; j <= right; j++)
       if(h[j] > x){
               i = i + 1;
               swap(i, j);
       }        
    swap(left, i);
    return i;
}

void qsort(int left, int right){
     if(left >= right)
       return;
     int poz = partitie(left, right);
     qsort(left, poz - 1);
     qsort(poz + 1, right);
}

int main(){
    
    freopen("gutui.in","r", stdin);
    freopen("gutui.out","w",stdout);
    int i;
    
    scanf("%d%d%d", &N, &H, &U);
    for(i = 0; i < N; i++){
          scanf("%d", &h[i]);
          scanf("%d", &g[i]);
    }
    
    qsort(0, N);
    
    int time = 0;
    for( i = 0; i < N; i++){
         if(time + h[i] <= H){
           G = G + g[i];
           time = time + U;
         }
    }
        
    printf("%d", G);   
          
    return 0;
}