Cod sursa(job #164116)

Utilizator znakeuJurba Andrei znakeu Data 23 martie 2008 15:52:43
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 50001
#define MAXT 1001

// incomplet?....

struct peste
{
	int p,t;	
};

peste v[MAXN];
int t[MAXT];
peste t2[MAXT];
int n,k,tt,tm=0;

int cmp(const void *a, const void *b)
{
	peste x=*(peste*)a,y=*(peste*)b;
	if (((double)x.p/(double)x.t) > ((double)y.p/(double)y.t))
		return -1;
	if (((double)x.p/(double)x.t) < ((double)y.p/(double)y.t))
		return 1;
	return 0;
}

int main ()
{
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	
	int i,j,l,rez=0;
	
	scanf("%d%d%d",&n,&k,&tt);
	
	for (i=0; i<n; i++)
	{
		scanf("%d%d",&v[i].p,&v[i].t);
		if (tm<v[i].t)
			tm=v[i].t;
	}
	
	qsort(v,n,sizeof(v[0]),cmp);
	
	for (i=1; i<=tm; i++)
	{
		for (j=0,l=0; j<n && l<k; j++)
			if (v[j].t<=i)
			{
				t[i]+=v[j].p;
				l++;
			}
		t2[i].p=t[i];
		t2[i].t=i;
	}
	
	qsort(t2,tm+1,sizeof(t2[0]),cmp);
	
	i=0;
	while (tt && i<tm)
	{
		rez+=tt/t2[i].t*t2[i].p;
		tt-=tt/t2[i].t*t2[i].t;
		i++;
	}
	
	printf("%d\n",rez);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}