Cod sursa(job #439862)

Utilizator dobreDobre Catalin Andrei dobre Data 11 aprilie 2010 20:00:53
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.91 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;
}
int pivot(int p, int q)
{
	int i,j, ii , jj;
	i = p;
	j = q;
	ii = 0;
	jj = -1;
	while ( i < j )
	{
		if ( mom[i] > mom[j] )
		{
			swap(&mom[i], &mom[j]);
			swap(&gre[i], &gre[j]);
			ii = (ii - 1 ) * -1;
			jj = (jj + 1)  * -1;
		}
		i += ii;
		j +=jj;
	}
	return i;
	
}
void quicksort(int p,int q)
{
	int m;
	if (p < q)
	{
		m = pivot(p, q);
		quicksort(p, m - 1);
		quicksort(m + 1, q);
	}
}

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");
	quicksort(0 , N - 1);
/*	for (int i = 0 ; i < N ; i++ )
		printf("%d ", mom[i]);
*/
//	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;
}