Cod sursa(job #163607)

Utilizator IoannaPandele Ioana Ioanna Data 22 martie 2008 14:48:37
Problema Peste Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 9-a Marime 1.47 kb
#include<stdio.h>
#include<math.h>
#include<string.h>
#define eps 0.0001
long n,k,tt;
long tp,np,tmax;
typedef struct {int p,t;}pesti;
pesti a[50005];
float rp[50005];
int x[50005],z[50005];

void scan()
{
scanf("%ld%ld%ld",&n,&k,&tt);
long i;
for (i=1;i<=n;i++)
    {
	 scanf("%d%d",&a[i].p,&a[i].t);
	 rp[i]=(float) a[i].p/a[i].t;
    }
}

long part(long st,long dr)
{
	float aux,p;
	pesti aux1,p1;
	long i,j;
	i=st-1;
	j=dr+1;
	p=rp[(st+dr)/2];
	p1=a[(st+dr)/2];
	while (1)
	{
		do{i++;} while (rp[i]-p>0 || (fabs(rp[i]-p)<eps && a[i].t<p1.t));
		do{j--;} while (rp[j]-p<0 || (fabs(rp[j]-p)<eps && a[j].t>p1.t));
		if (i<j)
		{
			aux=rp[i];
			rp[i]=rp[j];
			rp[j]=aux;
			aux1=a[i];
			a[i]=a[j];
			a[j]=aux1;
		}
	else return j;
	}
}

void quicks(long st,long dr)
{
	long p;
	if (st<dr)
	{
		p=part(st,dr);
		quicks(st,p);
		quicks(p+1,dr);
	}
}

void solve()
{
	long i,j,l;
	z[1]=1;
	for (i=0;i<=tt;i++)
	    {
			if (x[i+1]==0)
			   {memset(z,0,sizeof(z));
			    x[i]=0;
				tmax=0;
			   }
			while (x[i]<k)
			{
				for (j=1;j<=n;j++)
				{
					if (z[j]==0 && i+a[j].t<=tt)
					 break;
			    }
			  np+=a[j].p;
			  z[j]=1;
			  if (i+a[j].t>tmax)
				  tmax=a[j].t+i;
			  for (l=i;l<=tmax;l++)
				{
					x[l]++;	
				}
			}
			
			
	    }
}

int main()
{
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	scan();
	quicks(1,n);
	solve();
	printf("%ld\n",np);
	return 0;
}