Cod sursa(job #438468)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 10 aprilie 2010 19:49:05
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.22 kb
#include <stdio.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h> 
#include <algorithm>
#include <math.h>
using namespace std;
#define MAXX 100001

typedef struct DATE {
	unsigned long int a;
	unsigned long int b;
	} date;
	
date in[MAXX];
date out[MAXX];

bool comp(date one, date two)
{
	return one.a>one.b;
}

int main () {
	
	FILE *f,*g;
	f=fopen("gutui.in","r");
	g=fopen("gutui.out","w");
	unsigned long int n,h,u; 
	fscanf (f, "%lu %lu %lu",&n,&h,&u);
	char c[100];
	fgets(c,MAXX,f); // sa ajung pe urm linie
	unsigned long i,j;
	
	unsigned long int gmax=0; // greutatea maxima
	
	for (i=0;i<n;i++)
		fscanf (f, "%lu %lu",&in[i].a,&in[i].b);	

	sort(in,in+(n-1)*sizeof(date),comp);
	
	unsigned long int k = 0; //contor pt a numara cate elem voi avea in out
	for (i = 0; i < n;i ++ )
		if (in[i].a <= h) {
			out[k].a = in[i].a;
			out[k].b = in[i].b;
			gmax += in[i].b; 			 
			h -= u ; 
			k++;
		}
		else {
			int pozmin=0;
			for (j=1;j<k;j++) {				
				if (out[j].b < out[pozmin].b ) 
					pozmin=j;
			}			
			if (k !=0)
				if ( in[i].b > out[pozmin].b ) { 				
					gmax =gmax + in[i].b - out[pozmin].b;
					out[pozmin].a = in[i].a;
					out[pozmin].b = in[i].b;
				}
		}
	fprintf(g, "%lu\n",gmax);
		
		
	return 0;
}