Pagini recente » Cod sursa (job #1024935) | Cod sursa (job #1188059) | Cod sursa (job #702463) | Cod sursa (job #1294527) | Cod sursa (job #205133)
Cod sursa(job #205133)
#include <stdio.h>
#include <stdlib.h>
#define N 50010
int p[N],t[N];
int n,k,T;
void scan(void){
int i;
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d%d%d",&n,&k,&T);
for (i=1;i<=n;++i)
scanf("%d%d",&p[i],&t[i]);
}
int cmp(int a,int b){
if (t[a]!=t[b])
return t[a]-t[b];
return p[a]-p[b];
}
void swap_2(int i,int j){
int aux;
aux=p[i];
p[i]=p[j];
p[j]=aux;
aux=t[i];
t[i]=t[j];
t[j]=aux;
}
void down_heap_2(int i,int n){
int max=i;
if (2*i<=n && cmp(max,2*i)<0)
max=2*i;
if (2*i+1<=n && cmp(max,2*i+1)<0)
max=2*i+1;
if (i!=max){
swap_2(i,max);
down_heap_2(max,n);
}
}
void sort_t(void){
int i;
for (i=n/2;i>=1;--i)
down_heap_2(i,n);
for (i=n;i>1;--i){
swap_2(1,i);
down_heap_2(1,i-1);
}
}
int suma;
int h[N],nn,aux[N];
int TMAX;
int best[N];
void swap(int i,int j){
int auxa;
auxa=h[i];
h[i]=h[j];
h[j]=auxa;
}
void down_heap(int i,int n){
int max=i;
if (2*i<=n && h[max]>h[2*i])
max=2*i;
if (2*i+1<=n && h[max]>h[2*i+1])
max=2*i+1;
if (i!=max){
swap(i,max);
down_heap(max,n);
}
}
void update(int x){
if (nn<k){
h[++nn]=x;
suma+=x;
down_heap(1,nn);
return ;
}
if (x<h[1])
return ;
suma+=(x-h[1]);h[1]=x;
down_heap(1,nn);
}
void make_aux(){
int st=0,i;
for (i=1;i<=T;++i){
while (t[st+1]<=i && st<n){
update(p[++st]);
}
if (nn==k)
aux[i]=suma;
//printf("%d %d\n",i,st);
}
//for (i=1;i<=T;++i)
//printf("%d ",aux[i]);
TMAX=t[n];
}
int max(int a,int b){
if (a>b)
return a;
return b;
}
void solve_it(){
int i,j;
for (i=TMAX+1;i<=T;++i){
for (j=1;j<=TMAX;++j)
best[i]=max(best[i],best[i-j]+aux[j]);
}
}
void print_sol(){
if (T<=TMAX)
best[T]=aux[T];
printf("%d\n",best[T]);
fclose(stdin);
fclose(stdout);
exit(0);
}
int main(void){
scan();
sort_t();
make_aux();
solve_it();
print_sol();
}