Pagini recente » Cod sursa (job #2446640) | Cod sursa (job #856720) | Cod sursa (job #1168828) | Cod sursa (job #1634543) | Cod sursa (job #163650)
Cod sursa(job #163650)
#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;
}