Pagini recente » Cod sursa (job #163608) | Cod sursa (job #2222053) | Cod sursa (job #2040294) | Cod sursa (job #2950372) | Cod sursa (job #163604)
Cod sursa(job #163604)
#include<stdio.h>
#include<algorithm>
#define NMAX 50011
using namespace std;
long poz,ww,tc,j,in,mmax,sf,n,i,a,k,T,ii,rez,w,z[NMAX];
struct kkt
{
long P,T;
};
kkt xx[NMAX],x[NMAX],y[NMAX];
int cmpf1(const kkt a, const kkt b)
{
double A,B;
A=(double)a.P/a.T;
B=(double)b.P/b.T;
return ((A-B>0));
}
int cmpf2(const kkt a, const kkt b)
{
double A,B;
A=(double)a.P/a.T;
B=(double)b.P/b.T;
if (A-B>=0&&a.T>b.T)
return 1;
return 0;
}
int main()
{
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%ld%ld%ld",&n,&k,&T);
for (i=1;i<=n;i++)
{
scanf("%ld%ld",&x[i].P,&x[i].T);
xx[i]=x[i];
}
sort(x+1,x+n+1,cmpf1);
sort(x+1,x+n+1,cmpf2);
in=1;
sf=0;
tc=0;
while (tc<T)
{
y[++sf]=x[1];
z[1]=1;
for (j=2;j<=n&&sf-in+1<k;j++)
if (z[j]==0&&x[j].T+tc<=T&&x[j].T<=y[in].T)
{
z[j]=1;
y[++sf]=x[j];
y[sf].T+=tc;
}
mmax=-1;
rez+=y[in].P;
for (i=in;i<=sf;i++)
if (y[i].T>mmax)
mmax=y[i].T;
tc+=mmax;
mmax=10001;
for (i=in;i<=sf;i++)
if (mmax>y[i].T)
{
mmax=y[i].T;
poz=i;
}
in++;
}
for (i=in;i<=sf;i++)
rez+=y[i].P;
printf("%ld\n",rez);
return 0;
}