Pagini recente » Cod sursa (job #2464066) | Cod sursa (job #3243525) | Cod sursa (job #2714054) | Cod sursa (job #3216630) | Cod sursa (job #439460)
Cod sursa(job #439460)
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include<vector>
#include <functional>
//#include<sys/types.h>
using namespace std;
#define MAXX 1000000
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;
f=fopen("gutui.in","r");
g=fopen("gutui.out","w");
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
int i;
//int k = 0; //contor pt a numara cate gutui voi culege
vector<pair<unsigned long int,unsigned long int> > out; //heap in care memorez inaltimea si greutatea gutuilor culese
fscanf (f, "%lu %lu %lu",&n,&h,&u);
date aux;
for (i = 0; i < (int)n; i ++) {
fscanf (f, "%lu %lu",&aux.a,&aux.b);
in.push_back(aux);
}
sort(in.begin(),in.end(),comp2);
/*if (in[0].a <= h) {
out.push_back(make_pair(in[0].a, in[0].b));
push_heap(out.begin(),out.end(),comp) ;
if (h < u)
h = 0;
else
h -= u ;
}*/
for (i = 0; i < (int) n;i ++ )
if (in[i].a <= h) {
out.push_back(make_pair(in[i].a, in[i].b));
push_heap(out.begin(),out.end(),comp) ;
// printf ("**** \n");
//for (i=0; i<(int)out.size(); i++)
// printf (" %lu %lu \n", out[i].first,out[i].second);
// printf ("**** \n");
if (h < u)
h = 0;
else
h -= u ;
// k ++;
}
else {
if ( out.front().second < in[i].b) {
printf ("la la la \n");
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) ;
}
}
gmax=0;
for (i=0; i<(int)out.size(); i++)
gmax += out[i].second;
for (i=0; i<(int)out.size(); i++)
printf (" %lu %lu \n", out[i].first,out[i].second);
fprintf(g, "%lu\n",gmax);
return 0;
}