Cod sursa(job #441380)

Utilizator MikhinjaCatalina Mihai Vlad Mikhinja Data 12 aprilie 2010 21:38:43
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 1.28 kb
/*
Catalina Mihai Vlad
334CB
Problema - Gutui
Complexitate O(N^2)
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void){
int N,H,U,G=0,*h,*g,*m,i,j,aux,aux2;
FILE *f;
f=fopen("gutui.in","r");
fscanf(f,"%i%i%i",&N,&H,&U);
h=(int*)malloc(sizeof(int)*N);//inaltimile gutuilor
g=(int*)malloc(sizeof(int)*N);//greutatile gutuilor
m=(int*)malloc(sizeof(int)*N);//aici marcam fiecare gutuie culeasa
memset(m,0,N*sizeof(int));//demarcam toate gutuile
for(i=0;i<N;i++)
	fscanf(f,"%i%i",&h[i],&g[i]);
fclose(f);

for(i=0;i<N-1;i++)//sortare descrescatoare dupa inaltimi
	for(j=i+1;j<N;j++)
		if( h[i] < h[j] ){
			aux  = h[i];
			h[i] = h[j];
			h[j] = aux;
			aux  = g[i];
			g[i] = g[j];
			g[j] = aux;
		}

aux=0;//aux va contoriza cate gutui au fost culese
for(i=0;i<N;i++)
	if( h[i] + aux * U <= H ){
		m[i] = 1;
		G   += g[i];
		aux++;
	}
	else {aux2=i;
		for(j=i-1;j>=0;j--)
			if(m[j] && g[j] < g[aux2])
				aux2=j;
		if(aux2!=i){
			m[aux2]=0;
			m[i]   =1;
			G     += g[i] - g[aux2];
		}
	}
//for(i=0;i<N;i++){
//	printf("\ngutuie la %3i greutate %3i stat: ",h[i],g[i]);
//	if(m[i])
//		printf("Culeasa!");
//	else printf("neculeasa.");
//}printf("\n");
f=fopen("gutui.out","w");
fprintf(f,"%i",G);
fclose(f);
return 0;
}