Pagini recente » Cod sursa (job #2724021) | Cod sursa (job #689724) | Cod sursa (job #1348328) | Cod sursa (job #1087763) | Cod sursa (job #441251)
Cod sursa(job #441251)
/*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;
}