Pagini recente » Cod sursa (job #2656342) | Cod sursa (job #440316)
Cod sursa(job #440316)
//Ene Daniela 324CA
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include<vector>
#include <functional>
#define MAXX 1000000
using namespace std;
typedef struct DATE {
unsigned long int a;
unsigned long int b;
} date;
date in[MAXX];//memorez inaltimea si greutatea gutuilor din copac
void merge(int low, int high, int mid) {
int i, j, k;
unsigned long int c[MAXX],d[MAXX];
i = low;
j = mid+1;
k = low;
while((i <= mid)&&(j <= high)) { // sortez dupa in.a
if (in[i].a > in[j].a) {
c[k] = in[i].a;
d[k] = in[i].b;
k ++;
i ++;
}
else {
c[k] = in[j].a;
d[k] = in[j].b;
k ++;
j ++;
}
}
while(i <= mid) {
c[k] = in[i].a;
d[k] = in[i].b;
k ++;
i ++;
}
while(j <= high){
c[k] = in[j].a;
d[k] = in[j].b;
k ++;
j ++;
}
for(i = low;i < k;i ++) {
in[i].a = c[i];
in[i].b = d[i];
}
}
void mergesort( int low, int high) {
int mid;
if(low < high) {
mid = (low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,high,mid);
}
}
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 < n;i ++)
fscanf (f, "%lu %lu",&in[i].a,&in[i].b);
mergesort(0,n-1); //ordonez vectorul de structuri de tip date descrescator dupa inaltime
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;
}