Cod sursa(job #441251)

Utilizator Elena.Elena Diana Elena. Data 12 aprilie 2010 20:41:24
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.8 kb
/*BUCHIR Elena
     325CC*/

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct{
        long int h,g;
        int pas;
        }gutuie;
//functie care calculeaza minimul dintre doua numere intregi
int minim(int a, int b){
    if(a<b) return a;
    else return b;
}
//functie care compara doua gutui dupa inaltime
bool compara_gutuie(const gutuie &a, const gutuie &b)
{
//	gutuie * h1 = (gutuie*) a;
//gutuie * h2 = (gutuie*) b;
	return b.h - a.h;
	return 0;
}

int main(){
    FILE* f=fopen("gutui.in","r");
    FILE* p=fopen("gutui.out","w"); 
    
    long int N, H, U;
    fscanf(f,"%ld %ld %ld",&N,&H,&U); 
    
    int tmin=1,min;//in tmin am retinut de cate ori se poate inalta, maxim, gutuiul, pana in momentul prezent
    int i,j; 
   // gutuie x[100000];
   vector<gutuie> x;
   gutuie var;
    int sol[100000]; // greutatea maxima care se poate obtine la un anumit pas
    int max=0; //greutatea maxima finala
    sol[1]=0;
    for(i=0;i<N;i++){                                                                                                                                                                                                                                                  
                     fscanf(f,"%ld %ld",&var.h,&var.g);
                     x.push_back(var);
                     } //citire date de intrare
    std::sort(x.begin(),x.end(),compara_gutuie);   
    //qsort(x,N,sizeof(gutuie),compara_gutuie); //sortez vectorul de gutui descrescator dupa inaltime
    
    for(i=1;i<N;i++){
                     x[i].pas = (H-x[i].h) / U; //calculez pasul la care nu mai poate fi culeasa gutuia i
                     min = minim(x[i].pas,tmin);
                     for(j=min+1;j>=1;j--) //parcurg toti pasii anteriori si daca la pasul j culeg gutuia i
                                           //si obtin o greutate mai buna decat cea dinainte, o retin ca fiind cea mai buna solutie 
                                           //partiala pana la pasul j
                                          if((sol[j-1]+x[i].g) > sol[j]){
                                                                      sol[j] = sol[j-1]+x[i].g;
                                                                      if(sol[j] > max)
                                                                           max = sol[j];
                                                                      if(j == min+1)
                                                                           tmin ++;
                                                                           }
                     }
                     
   //afisez maximul               
    fprintf(p,"%d",max);
    fclose(f);
    fclose(p);
    return 0;
}