Pagini recente » Cod sursa (job #1314978) | Cod sursa (job #2844892) | Cod sursa (job #2956983) | Cod sursa (job #1077852) | Cod sursa (job #163607)
Cod sursa(job #163607)
#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;
}