Cod sursa(job #436778)
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstdlib>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
typedef struct {
int greutate;
int inaltime;
} gutuie;
bool comp1(gutuie g1, gutuie g2){
return (g1.inaltime > g2.inaltime);
}
bool comp2(gutuie g1, gutuie g2){
return (g1.greutate < g2.greutate);
}
void rezultat(vector<gutuie> g, FILE *f){
vector<gutuie>::iterator it;
int total = 0;
for(it = g.begin(); it != g.end(); it++)
total += it->greutate;
fprintf(f, "%d", total);
}
int main(){
FILE *in = fopen("gutui.in", "r");
FILE *out = fopen("gutui.out", "w");
int n,h,u,i;
fscanf(in, "%d %d %d", &n, &h, &u);
int ch = h; //copie a lui h
vector<gutuie> gut, cos;
vector<gutuie>::iterator it;
gutuie g;
char *aux = (char*) malloc (100 * sizeof(char));
fgets(aux, 100, in); // sar peste linia curenta
for(i = 0; i < n; i++){
fscanf(in, "%d %d", &g.inaltime, &g.greutate);
gut.push_back(g);
fgets(aux, 100, in); //sar peste linia curenta
}
// sortez descrescator vectorul de gutui dupa inaltime
sort(gut.begin(), gut.end(), comp1);
for(it = gut.begin(); it != gut.end(); it++){
if(it->inaltime <= ch){ // daca pot ajunge la gutuie
cos.push_back(*it); // atunci o adaug in cos
ch -= u; // inaltimea maxima la care pot ajunge scade cu U cm
}
}
// daca am reusit sa culeg toate gutuile atunci afisez greutatea cosului
if(gut.size() == cos.size()){
rezultat(cos, out);
return 0;
}
// acum imi creez vectorul care contine gutuile care nu sunt in cos
vector<gutuie>::iterator it2;
for(it = cos.begin(); it != cos.end(); it++)
for(it2 = gut.begin(); it2 != gut.end(); it2++)
if(it2->inaltime == it->inaltime &&
it2->greutate == it->greutate){
gut.erase(it2);
break;
}
// fac un minheap al cosului ordonat dupa greutati
make_heap(cos.begin(), cos.end(), comp2);
/*for(it = cos.begin(); it != cos.end(); it++)
cout << " " << it->inaltime << "->" << it->greutate;
*/
// acum analizez gutuile care n-au intrat in cos
for(it2 = gut.begin(); it2 != gut.end(); it2++){
// daca greutatea gutuii analizate este mai mare decat greutatea
// celei mai usoare gutui din cos atunci...
if(it2->greutate > cos.front().greutate){
cos.front() = *it2;
sort_heap(cos.begin(), cos.end(), comp2);
}
}
rezultat(cos, out);
free(aux);
fclose(in);
fclose(out);
return 0;
}