Pagini recente » Cod sursa (job #1966488) | Cod sursa (job #2403756) | Cod sursa (job #3263027) | Borderou de evaluare (job #255655) | Cod sursa (job #164116)
Cod sursa(job #164116)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 50001
#define MAXT 1001
// incomplet?....
struct peste
{
int p,t;
};
peste v[MAXN];
int t[MAXT];
peste t2[MAXT];
int n,k,tt,tm=0;
int cmp(const void *a, const void *b)
{
peste x=*(peste*)a,y=*(peste*)b;
if (((double)x.p/(double)x.t) > ((double)y.p/(double)y.t))
return -1;
if (((double)x.p/(double)x.t) < ((double)y.p/(double)y.t))
return 1;
return 0;
}
int main ()
{
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
int i,j,l,rez=0;
scanf("%d%d%d",&n,&k,&tt);
for (i=0; i<n; i++)
{
scanf("%d%d",&v[i].p,&v[i].t);
if (tm<v[i].t)
tm=v[i].t;
}
qsort(v,n,sizeof(v[0]),cmp);
for (i=1; i<=tm; i++)
{
for (j=0,l=0; j<n && l<k; j++)
if (v[j].t<=i)
{
t[i]+=v[j].p;
l++;
}
t2[i].p=t[i];
t2[i].t=i;
}
qsort(t2,tm+1,sizeof(t2[0]),cmp);
i=0;
while (tt && i<tm)
{
rez+=tt/t2[i].t*t2[i].p;
tt-=tt/t2[i].t*t2[i].t;
i++;
}
printf("%d\n",rez);
fclose(stdin);
fclose(stdout);
return 0;
}