Cod sursa(job #435105)

Utilizator points_hunterAdrian Dobrescu points_hunter Data 6 aprilie 2010 22:04:10
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.06 kb
#include<stdio.h>
#define min(i, x) (((i) < (x))?(i):(x))
 
int i, j, N, H, U;
int *h, *g, *sol;


//h - inaltimile gutuilor, g - greutatile
//t[i] - greutatea maxima care se poate obtine la momentul de timp i;

//functie de interschimbare 
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;
}
 
//pozitioneaza pivotul de pe prima pozitie a.i.
//in stanga sunt toate elementele mai mici decat el
//in dreapta, toate elementele mai mari decat el
int partitie(int left, int right){
    int i, j, x = (H - h[left])/U;
    i = left;
    for(j = left + 1; j <= right; j++)
       if((H - h[j])/U < x || ((H-h[j])/U == x && g[j] > g[left])){
               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;
    
    //citire
    scanf("%d%d%d", &N, &H, &U);
    
    h = (int *)calloc(N + 1, sizeof(int));
    g = (int *)calloc(N + 1, sizeof(int));
    sol = (int *)calloc(N + 1, sizeof(int)); 
    
    for(i = 0; i < N; i++){
        scanf("%d", &h[i]);
        scanf("%d", &g[i]);
    }
    
    //se sorteaza gutuile in ordine crescatoare dupa momentul de timp la care
    //le PIERD
    qsort(0, N);
     
    int t = 0, max = 0; 
    
    for(i = 0; i < N && H - h[i] < 0; i++);
    
    for(; i < N; i++)
        for(j = min(t, (H - h[i])/U); j >= 0; j--)
             if(g[i] + sol[j] > sol[j+1]){
                   if(j == t)
                      t++;
                   sol[j+1] = g[i] + sol[j];
                   if(sol[j+1]>max)
                      max = sol[j+1];
             }
             else
                 break;
                    
    //se afiseaza maximul
    printf("%d", max); 
           
    return 0;
}