Pagini recente » Cod sursa (job #2835668) | Cod sursa (job #1542635) | Cod sursa (job #2242127) | Cod sursa (job #1547282) | Cod sursa (job #439569)
Cod sursa(job #439569)
//Ene Daniela 324CA
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include<vector>
#include <functional>
using namespace std;
typedef struct DATE {
unsigned long int a;
unsigned long int b;
} date;
vector<date> in;//memorez inaltimea si greutatea gutuilor din copac
bool comp(pair<unsigned long int,unsigned long int>i,pair<unsigned long int,unsigned long int>j) {
return(i.second>j.second);
}
bool comp2 (date aa, date bb) {
return(aa.a > bb.a);
}
int main () {
FILE *f,*g;
unsigned long int n,h,u; // n:numar de gutui h: inamtimea max u:cu cat se ridica crengile
unsigned long int gmax=0; // greutatea maxima
vector<pair<unsigned long int,unsigned long int> > out; //heap in care memorez inaltimea si greutatea gutuilor culese
date aux;
int i;
f=fopen("gutui.in","r");
g=fopen("gutui.out","w");
fscanf (f, "%lu %lu %lu",&n,&h,&u);
for (i = 0; i < (int)n; i ++) {
fscanf (f, "%lu %lu",&aux.a,&aux.b);
in.push_back(aux);
}
//ordonez vectorul de structuri de tip date descrescator dupa inaltime
sort(in.begin(),in.end(),comp2);
for (i = 0; i < (int) n;i ++ )
//daca mai pot culege gutui culeg in continuare
if (in[i].a <= h) {
out.push_back(make_pair(in[i].a, in[i].b));
push_heap(out.begin(),out.end(),comp) ;
if (h < u)
h = 0;
else
h -= u ;
}
else {
//verific daca una din gutuile culese deja pot fi poate fi inlocuita de gutuia curenta
if ( out.front().second < in[i].b) {
pop_heap( out.begin( ), out.end( ), comp );
out.pop_back();
out.push_back(make_pair(in[i].a,in[i].b));
push_heap(out.begin(),out.end(),comp) ;
}
}
//calculez greutatea max a tuturor gutuilor culese
for (i=0; i<(int)out.size(); i++)
gmax += out[i].second;
fprintf(g, "%lu\n",gmax);
return 0;
}