Pagini recente » Cod sursa (job #1253371) | Cod sursa (job #543913) | Cod sursa (job #33524) | Cod sursa (job #2190957) | Cod sursa (job #163548)
Cod sursa(job #163548)
#include <stdio.h>
#include <stdlib.h>
long n,k,T,i,j,v[50005];
long tmax,max,q,l;
long a[1005],p[50005],t[50005],ind[50005];
int comp(const void * n1, const void *n2){
return (p[*((long*)n1)]-p[*((long*)n2)]);
}
int main(){
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%ld %ld %ld",&n,&k,&T);
tmax=0;
for (i=1;i<=n;i++){
scanf("%ld %ld",&p[i],&t[i]);
if (t[i]>tmax)tmax=t[i];
ind[i]=i;
}
qsort(ind+1,n,sizeof(long),comp);
for (j=1;j<=tmax;j++){
a[j]=0;
q=0;i=n+1;
while (q<k&&i>1){
i--;
if (t[ind[i]]<=j){a[j]+=p[ind[i]];q++;}
}
}
for (i=0;i<T;i++){
l=T-i;
if (tmax<l)l=tmax;
for (j=1;j<=l;j++)
if (v[i]+a[j]>v[i+j])v[i+j]=v[i]+a[j];
}
max=0;
for (i=1;i<=T;i++)
if (max<v[i])max=v[i];
printf("%ld\n",max);
return 0;
}