Pagini recente » Cod sursa (job #2526889) | Cod sursa (job #2463159) | Cod sursa (job #1138024) | Cod sursa (job #2385713) | Cod sursa (job #439262)
Cod sursa(job #439262)
#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;
date in[MAXX]; //memorez inaltimea si greutatea gutuilor din copac
//date out[MAXX]; //memorez inaltimea si greutatea gutuilor culese
/*
bool comp(pair<unsigned long int,unsigned long int>i,pair<unsigned long int,unsigned long int>j) {
return(i.second>j.second);
}
*/
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);
}
}
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;
fscanf (f, "%lu %lu %lu",&n,&h,&u);
for (i = 0; i < (int)n; i ++)
fscanf (f, "%lu %lu",&in[i].a,&in[i].b);
mergesort(0,n-1);
//pentru fiecare elem din hi vad daca pot sa il adaug la structura
//daca nu il pot aduaga, vad ce element as putea inlocui in structura ai structura sa aiba greutate maxima
for (i = 0; i < (int) n;i ++ )
if (in[i].a <= h) {
out.push_back(make_pair(in[i].a, in[i].b));
if (h < u)
h = 0;
else
h -= u ;
// k ++;
}
else {
if ( out.front().second < in[i].b) {
pop_heap( out.begin( ), out.end( ), greater<pair<unsigned long int,unsigned long int> > ( ) );
out.pop_back();
out.push_back(make_pair(in[i].a,in[i].b));
push_heap(out.begin(),out.end()) ;
}
}
for (i=0; i<(int)out.size(); i++)
gmax += out[i].second;
fprintf(g, "%lu\n",gmax);
return 0;
}