Cod sursa(job #436739)

Utilizator dodgerblueBogdan P. dodgerblue Data 8 aprilie 2010 21:30:03
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 1.4 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>

using namespace std;

int N,H,U;

typedef struct {
		int h,g;
} gutuie;

gutuie *gutui;

FILE *f,*g;

bool comp(gutuie c1, gutuie c2) { 
	if(c1.h > c2.h)
		return true;
	if(c1.h == c2.h && c1.g > c2.g)
		return true;
	return false;
}

bool comp2(gutuie c1, gutuie c2){
	return c1.g > c2.g;
}

void afisare(){
		int i;
		for(i=0;i<N;i++)
			printf("Gutuia %d: h = %d g = %d\n",i+1,gutui[i].h,gutui[i].g);
		printf("--------------\n");
}

int main(){
	
	int i,k,hc;
	int max = 0;
	
	f = fopen("gutui.in","r");
	g = fopen("gutui.out","w");
	
	fscanf(f,"%d %d %d\n",&N,&H,&U);
	gutui = (gutuie*)calloc(N,sizeof(gutuie));
	
	for(i=0;i<N;i++)
		fscanf(f,"%d %d\n",&gutui[i].h,&gutui[i].g);
		
	//afisare();
	sort(gutui,gutui+N,comp);
	//afisare();
	
	//se elimina gutuile care sunt la inaltimi mai mari de H
	k=0;
	while(gutui[k].h>H)
		k++;
	for(i=0;i<N-k;i++)
		gutui[i]=gutui[i+k];
	N=N-k;
	//afisare();
	
	k = 1;
	hc = H;
	i = 0;
	
	while(i<N){
			while(gutui[i].h<=hc && gutui[i].h>(hc-U) && i<N){
				gutui[i].h = k;
				i++;
			}
			hc = hc - U;
			k++;
	}
	
	//afisare();
	
	sort(gutui,gutui+N,comp2);
	
	//afisare();
	
	k = 0;
	while(k<N){
		if(gutui[k].h>0){
			hc = gutui[k].h;
			max = max + gutui[k].g;
			for(i=k+1;i<N;i++)
				if(gutui[i].h>=hc)
					gutui[i].h--;
		}
		k++;
	}
	
	fprintf(g,"%d\n",max);
	
	fclose(f);
	fclose(g);
	return 0;
	
}