Cod sursa(job #442691)

Utilizator carl1ontzataBacioi Florentina carl1ontzata Data 14 aprilie 2010 23:13:41
Problema Gutui Scor 60
Compilator cpp Status done
Runda teme_upb Marime 1.85 kb
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define INF 100000
using namespace std;

void sortare(int x[],int y[],int n)
{
 int temp,tempor,i,j;
 for(i=0;i<n-1;i++)
 for(j=i+1;j<n;j++)
         if (x[i]<x[j]){
            temp=x[i];
            x[i]=x[j];
            x[j]=temp;
            tempor=y[i];
            y[i]=y[j];
            y[j]=tempor;
            }
}

int main()
{
	int N, H, U;	// nr. gutui, inaltime maxima, cu cat se ridica
	int nn;
  
	int i, j, min, poz, maxim = -INF;
	int *Number, *Sum, *renunt;
	
	FILE *f1,*f2;
    f1=fopen("gutui.in","r");
    f2=fopen("gutui.out","w");
    fscanf(f1,"%d %d %d",&N,&H,&U);
    int  u[N+1], g[N+1];
    for(i=0;i<N;i++)
              fscanf(f1,"%d %d",&u[i],&g[i]);
	
	
	
	// sortat descrescator dupa inaltime
	sortare(u,g,N);
	
	renunt = (int *)malloc(N * sizeof(int));
	Sum = (int *)malloc(N * sizeof(int));
	Number = (int*)malloc(N * sizeof(int));
	

	Sum[0] = g[0];
	Number[0] = 1;
	
	for(i = 1; i < N; i++)
	{
		//	cout<<height[i] + NrGutui[i - 1] * u<<" ";
		if((u[i] + Number[i - 1] * U) <= H)
		{
			Sum[i] = Sum[i - 1] + g[i];
			Number[i] = Number[i - 1] + 1;
		}
		else
		{
			// Nu poti sa culegi gutuia i
			Number[i] = Number[i - 1];
			Sum[i] = Sum[i - 1];
			min = INF;
			poz = 0;
			
			// Incerci sa renunti la una culeasa, astfel incat daca ai renunta la ea
			// si ai culege gutuia i, ai avea un profit mai mare
			for(j = 0; j < i; j++)
				if((renunt[j] == 0) && (min > g[j]))
				{
					min = g[j];
					poz = j;
				}
				
			if(min < g[i])
			{
				renunt[poz] = 1;
				Sum[i] = Sum[i - 1] -g[poz] + g[i];
			}
			else
				renunt[i] = 1;
		}
		//cout<<Sol[i]<<" "<<NrGutui[i]<<"\n" ;
	}	
				
	fprintf(f2,"%d",Sum[N-1]);				
				
	fclose(f1);
	fclose(f2);
	return 0;
}