Cod sursa(job #437745)

Utilizator dragosiordachedragos iordache dragosiordache Data 10 aprilie 2010 00:58:48
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 0.9 kb
#include "stdio.h"
#include "stdlib.h"

typedef struct {
	int h,g;
} gutui;

int cmp(void* a, void* b)
{
	return ((gutui*)b)->g - ((gutui*)a)->g;
}

int main() 
{
	FILE *f, *g;
	f = fopen("gutui.in", "r");
	g = fopen("gutui.out", "w");
	int n,i;
	int h,u;

	fscanf(f, "%i %i %i", &n,&h,&u);
	gutui a[n];

	for (i=0;i<n;i++)
		fscanf(f, "%i %i", &a[i].h, &a[i].g);

	qsort(a, n, sizeof(gutui), cmp);
	
	int c[h/u+1];
	for (i=0;i<=h/u;i++)
		c[i]=0;
	unsigned int tot=0;
	int contor = 0,j,k;
	int boo = 0;
	for (j=0;j<n && contor<h/u+1;j++)
	{
		c[(h-a[j].h)/u]++;//vad daca gutuia curenta poate intra la solutie
		for (i=0,boo=1,k=-1;i<h/u+1 && boo;i++)
		{
			k+=c[i];
			if (k>i) boo = 0;//verific daca dupa ce o adaug la solutie poate fi culeasa
		}
		if (boo)
		{
			tot+=a[j].g;				
			contor++;
		}
		else
		{
			c[(h-a[j].h)/u]--;//daca nu
		}
	}
	fprintf(g, "%u", tot);

	fclose(f);
	fclose(g);
	
	return 0;
}