Cod sursa(job #163650)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 22 martie 2008 14:51:49
Problema Peste Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 10-a Marime 1.15 kb
#include<stdio.h>
#include<string.h>
#define M 50000

int p[M],t[M];
long sol[M][2],n,k,i,j,ttot,l,ok,q,qq,maxx;

long max(long a,long b)
{	if (a>b) return a;
	else	return b;
}

void qsort(long l,long r)
{long i,j,x,y;
	i=l;j=r;
	x=t[(l+r)/2]/p[(l+r)/2];
	do
	{
		while (t[i]/p[i]<x) i++;
		while (x<t[j]/p[j]) j--;
		if (i<=j)
		{
			y=p[i];p[i]=p[j];p[j]=y;
			y=t[i];t[i]=t[j];t[j]=y;
			i++;j--;
		}
	}
	while (i<=j);
	if (l<j) qsort(l,j);
	if (i<r) qsort(i,r);
}


int main()
{
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	scanf("%ld %ld %ld",&n,&k,&ttot);
	for (i=1;i<=n;i++)
		scanf("%ld %ld",&p[i],&t[i]);

	qsort(1,n);
	for(i=1;i<=ttot;i++)
	{
		if (sol[0][0]<k)
		for (j=1;j<=n;j++)
		{
			ok=1;
			for (q=1;q<=sol[0][0];q++)
				if (sol[q][0]==j)
					ok=0;
			if (ok)
			{
				sol[0][0]++;sol[sol[0][0]][0]=j;
				sol[sol[0][0]][1]=t[j];
				maxx+=p[j];
				break;
			}
		}
		for(qq=1;qq<=sol[0][0];qq++)
			if (--sol[qq][1]==0)
			{
				for (q=qq+1;q<=sol[0][0];q++)
				    sol[q-1][0]=sol[q][0];
				sol[0][0]--;
				qq--;
			}
	}
	printf("%ld\n",maxx);
	return 0;
}