Pagini recente » Rating vasile andrei mihai (andybmx20) | Cod sursa (job #1475983) | Cod sursa (job #2246268) | Cod sursa (job #1181391) | Cod sursa (job #1856016)
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define t first
#define p second
using namespace std;
FILE * fin = fopen("peste.in", "r");
FILE * fout = fopen("peste.out", "w");
int n, k, T, best[50005], sum;
long long d[50005];
pair<int,int> v[50005];
priority_queue< int, vector<int>, greater<int> > q;
int main(){
fscanf( fin, "%d%d%d", &n, &k, &T );
for( int i = 1; i <= n; i++ ){
fscanf( fin, "%d%d", &v[i].p, &v[i].t );
}
sort( v + 1, v + n + 1 );
sum = 0;
for( int i = 1; i <= n; i++ ){
sum += v[i].p;
q.push( v[i].p );
if( q.size() > k ){
sum -= q.top();
q.pop();
}
best[ v[i].t ] = max( best[ v[i].t ], sum );
}
best[0] = 0;
for( int i = 1; i <= T; i++ ){
best[i] = max( best[i], best[i - 1] );
}
d[0] = 0;
for( int i = 1; i <= T; i++ ){
for( int j = i - 1; j >= 0; j-- ){
d[i] = max( d[i], d[j] + 1LL * best[i - j] );
}
}
fprintf( fout, "%lld", d[T] );
return 0;
}