Pagini recente » Cod sursa (job #22474) | Cod sursa (job #1696039) | Cod sursa (job #1296245) | Cod sursa (job #1938931) | Cod sursa (job #1856326)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <queue>
#define N 50100
#define INF -1
#define T 1001
using namespace std;
struct plasa {
int p , t ;
};
plasa pls [ N ] ;
int fish [ N ] ;
int best [ N ] ;
long long sol [ N ];
bool cmp ( plasa a , plasa b ){
return a.t < b.t ;
}
priority_queue < int > que ;
int main(){
int n , k , tmax , i , j ,id ;
int sum = 0 ,tpls = 0 ;
freopen("peste.in","r",stdin );
freopen("peste.out","w",stdout );
scanf("%d%d%d", &n , &k , &tmax );
for ( i = 0 ; i < n ; i ++ ){
scanf("%d%d",&pls[ i ].p , &pls [ i ].t );
if ( pls [ i ].t > tpls ){
tpls = pls [ i ].t ;
}
}
sort ( pls , pls + n , cmp );
int nr = 0 , nrp ;
for ( i = 0 , nrp = 0 ; i <= tpls ; i ++ ){
while ( pls[ nrp ]. t == i && nrp < n ){
sum += pls [ nrp ] . p ;
que. push ( -pls [ nrp ]. p );
nr ++ ;
nrp ++ ;
}
while ( nr > k ){
sum += que.top();
que.pop() ;
nr-- ;
}
best [ i ] = sum ;
}
for ( i = 0 ; i <= tmax ; i ++ ){
sol [ i ] = INF ;
}
sol [ 0 ] = 0 ;
for ( i = 0 ; i <= tmax ; i ++ ){
for ( j = 1 ; j <= tpls && i - j >= 0 ; j ++ ){
sol[ i ] = max ( sol [ i ] , sol [ i - j ] + best [ j ] );
}
// for ( j = tmax - pls [ i ] .t ; j >=0 ; j -- ){
//
// if ( sol [ j ] == INF ){
// continue ;
// }
//
// if ( sol[ j + pls [ i ].t ] < sol [ j ] + best [ i ] ){
// sol[ j + pls [ i ].t ] = sol [ j ] + best [ i ] ;
// }
//
// for ( id = j + 2 * pls [ i ].t ; id <= tmax ; id += pls [ i ].t ){
//
// if ( sol [ id ] < sol [ id - pls[ i ].t ] + best [ i ] ){
// sol [ id ] = sol [ id - pls[ i ].t ] + best [ i ] ;
// }else {
// break ;
// }
//
// }
//
// }
}
for ( i = 0 ; i <= tmax ; i ++ ){
sol[ tmax ] = max ( sol [ i ] , sol [ tmax ] ) ;
}
if ( sol [ tmax ] == -1 ){
printf("0");
return 0 ;
}
printf("%lld",sol[ tmax ] );
return 0;
}