Cod sursa(job #438777)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <functional>
//#include <conio.h>
using namespace std;
int n,h,u;
//structura pentru retinerea datelor de intrare
typedef struct {
unsigned int height;
unsigned int weight;
unsigned int clas; //variabila care imi indica pasul maxim la care
}gutuie; //poate fi culeasa o gutuie
gutuie *vect;
//functie care compara doua gutui dupa greutate
bool my_compare(const gutuie &a,const gutuie &b){
// gutuie *unu=(gutuie *) a;
// gutuie *doi=(gutuie *) b;
return (b.weight > a.weight);
}
int main(){
int i,j,max_dif=0,k=0,nrgutui=0,sum=0;
int *solutie;
FILE *fin=fopen("gutui.in","r");
FILE *fout=fopen("gutui.out","w");
fscanf(fin,"%d",&n);
fgetc(fin);
fscanf(fin,"%d",&h);
fgetc(fin);
fscanf(fin,"%d",&u);
//respect restrictile
if(n<1||n>100000)
return 1;
vect=(gutuie *)malloc(n*sizeof(gutuie));
//citesc datele de intrare
for(i=0;i<n;i++){
fgetc(fin);
fscanf(fin,"%d",&vect[i].height);
//verific daca gutuia poate fi culeasa
if(vect[i].height<=h){
fgetc(fin);
fscanf(fin,"%d",&vect[i].weight);
vect[i].clas=(h-vect[i].height)/u+1;
if(vect[i].clas>max_dif) //vad cate gutui pot culege maxim
max_dif=vect[i].clas;
}
else {
i--;
n--;
}
}
//vector care are pe pozitia i greutatea gutui care a fost culeasa la pasul i
//initializat cu 0
solutie=(int *)calloc(max_dif+1,sizeof(int));
//sortez dupa greutate
std::sort(vect,vect+n+1,my_compare);
//qsort(vect,n,sizeof(gutuie),my_compare);
//incep sa culeg gutui cat mai grele pana am cules destule
for(i=0;i<n && nrgutui<=max_dif;i++){
k=vect[i].clas;
if(solutie[k]==0){ //nu am mai cules gutuie la pasul k
solutie[k]=vect[i].weight;
nrgutui++;
}
else
for(j=k-1;j>=0;j--) //am cules gutuie la pasul k si incerc
if(solutie[j]==0){ //sa culeg gutuia curenta anterior
solutie[j]=vect[i].weight;
nrgutui++;
break;
}
}
/*
metoda pe care am abordat-o prima data
dar care era prea lenta datorita qsortului de mai jos
in teorie si ea functioneaza
while(i<n){
k=vect[i].clas;
for( g=depl ; g < k && i < n; g++)
solutie[depl++]=vect[i++].weight;
schimb=0;
qsort(solutie,depl,sizeof(int),comp);
for(g=i;vect[g].clas==k&&schimb<k;g++)
for(j=0;j<depl&&schimb<k;j++)
if(solutie[j]<vect[g].weight) {
solutie[j]=vect[g].weight;
schimb++;
break;
}
i=g;
}
*/
//calculez greutatea maxima
for(i=1;i<=max_dif;i++)
sum+=solutie[i];
fprintf(fout,"%d",sum);
return 0;
}