Cod sursa(job #441018)

Utilizator yo2010yooo yooo yo2010 Data 12 aprilie 2010 18:43:55
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.36 kb
#include<stdio.h>
#define min(i, x) (((i) < (x))?(i):(x))
 
int i, j, N, H, U, tN;
int h[100000], g[100000], t[100000];

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

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;
    
    //citire
    scanf("%d%d%d", &N, &H, &U);
    for(i = 0; i < N; i++){
          scanf("%d", &h[i]);
          scanf("%d", &g[i]);
    }
    
    //se sorteaza gutuile in ordine descrescatoare dupa inaltime
    //(la inceput, cele care se pierd cel mai devreme)
    qsort(0, N);
     
    t[1] = g[0];
    
    //tmin = de cate ori se poate ridica, maxim, gutuiul, p?n? ?n momentul prezent
    int x, max = g[0], minim, tmin = 1;
     
    for( i = 1; i < N; i++){ //parcurg gutuile
         x = (H - h[i]) / U; //la al catelea moment de timp, pierd gutuia i.
         minim = min(x, tmin);
         for( j = minim + 1; j >= 1; j--)
              // parcurg toate momentele de timp anterioare
         
              if((t[j - 1] + g[i]) > t[j]){
                     /*daca la momentul j, culeg gutuia i si obtin o 
                     greutate mai buna decat cea precedenta, atunci o retin 
                     ca fiind cea mai buna solutie partiala, pana la momentul j*/
                     t[j] = t[j - 1] + g[i];
                     if(t[j] > max)// daca e cea mai buna solutie gasita
                        max = t[j];
                     if(j == minim + 1) // daca am putut lega gutuia i de cel
                     //mai mare moment de timp, atunci incrementez tmin.
                       tmin ++;
              }
    }
     
    //se afiseaza maximul
    printf("%d", max); 
    getchar();
    getchar();
    return 0;
}