Cod sursa(job #439823)

Utilizator dobreDobre Catalin Andrei dobre Data 11 aprilie 2010 19:34:19
Problema Gutui Scor 70
Compilator cpp Status done
Runda teme_upb Marime 1.43 kb
#include <stdio.h>
#define MAXN 100000
int N,Hmax, U;
int MaxTime;
int gre[MAXN];	// Tinem greutatile
int mom[MAXN];  // Ultimul moment in care se poate lua Gutui
int best[MAXN];
void Input(char* filename)
{
	FILE *f = fopen(filename , "r");
	fscanf(f, "%d%d%d", &N , &Hmax , &U);
	for (int i = 0 ; i < N ; i++){
		int h , g;
		fscanf(f,"%d%d", &h , &g);
		gre[i] = g;
		mom[i] = (Hmax - h) / U ;
		
		best[i] = 0;	//initializam peste tot cu 0
	}
	fclose(f);
}
void swap(int* a , int* b)
{
	int aux = *a;
	*a = *b;
	*b = aux;
}
void Sort()
{
	for (int i = 0 ; i < N - 1; i++)
		for (int j = i + 1 ; j < N ; j++)
			if (mom[i] > mom[j])
			{
				swap(&mom[i] , &mom[j]);
				swap(&gre[i] , &gre[j]);
			}
}
// Returneaza pozitia valoarii minima gasita n best pe [0 , index]
int GetPos(int index)
{
	int pos = index;
	for (int i = index; i >= 0 ; i--)
	{
		if (best[pos] > best[i])
			pos = i;
	}
	return pos;
}
void Solve()
{
	for (int i = 0 ; i < N ; i++)
	{
		int pos = GetPos(mom[i]);
		if (best[pos] < gre[i])
			best[pos] = gre[i];
	}
}
void Output(char *filename)
{
	FILE *f = fopen("gutui.out", "w");
	int sol = 0;
	for (int i = 0 ; i < N ; i++)
		sol += best[i];
	fprintf(f,"%d", sol);
	fclose(f);
}
int main(void)
{
	Input("gutui.in");
	Sort();
/*
	puts("Moment");
	for (int i = 0 ; i < N ; i++ )
		printf("%d ", mom[i]);
	puts("\nGreutate");
	for (int i = 0 ; i < N ; i++ )
		printf("%d ", gre[i]);
	puts("");*/
	Solve();
	Output("gutui.out");
	return 0;
}