Cod sursa(job #436868)

Utilizator CreationDinescu Stefan Creation Data 9 aprilie 2010 00:23:45
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.61 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct{
	int inaltime;
	int greutate;
}gutui;

/*int compare (const void *a, const void *b){
	const gutui *item1=a,*item2=b;
	if (item1->inaltime <item2->inaltime)
		return 1;
	else if (item1->inaltime > item2->inaltime)
		return -1;
	else
		return 0;
}*/

int compare (const void *a, const void *b){
	gutui *item1 = (gutui*)a;
	gutui *item2 = (gutui*)b;
	
	//printf("ggggg %d\n",item1->inaltime);
	
	return -(item1->inaltime - item2->inaltime);
}

int main(){
	FILE *fin=fopen("gutui.in","r");
	FILE *fout=fopen("gutui.out","w");
	
	int n,h,u;
	int i,curent=0,temp,ii;
	int total=0,max;
	
	fscanf(fin,"%d %d %d",&n,&h,&u);
	
	gutui *v=(gutui*)malloc(n*sizeof(gutui));
	int *x=(int*)malloc(n*sizeof(int));
	
	for (i=0;i<n;i++)
		fscanf(fin,"%d %d",&v[i].inaltime,&v[i].greutate);
		
	qsort(v,n,sizeof(gutui),compare);
	
	//for (i=0;i<n;i++)
		//printf("%d %d\n",v[i].inaltime,v[i].greutate);
	curent=h;	
	while (1){
		max=0;
		if (curent<v[n-1].inaltime)
			break;
		for (i=0;i<n;i++){
			if (max<v[i].greutate && v[i].inaltime<=curent && v[i].inaltime>curent-u && x[i]==0){
				ii=i;
				max=v[i].greutate;
			}
		}
		if (max==0){
			for (i=0;i<n;i++)
				if (v[i].inaltime<=curent && x[i]==0){
					temp=v[i].inaltime;
					break;
				}
			for (i=0;i<n;i++)
				if (max<v[i].greutate && v[i].inaltime<=temp && v[i].inaltime>temp-u && x[i]==0){
					ii=i;
					max=v[i].greutate;
				}
		}
		/*if (x[ii]==0)
			fprintf(fout,"ggg %d %d\t%d\n",v[ii].inaltime,v[ii].greutate,curent);*/
		total+=max;
		x[ii]=1;
		curent-=u;
	}	
	fprintf(fout,"%d",total);
	fclose(fin);
	fclose(fout);
	free(v);
	return 0;
}