Pagini recente » Cod sursa (job #1907849) | Monitorul de evaluare | Cod sursa (job #586364) | Cod sursa (job #792373) | Cod sursa (job #1855997)
#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
#define t first
#define p second
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
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(){
fin >> n >> k >> T;
for( int i = 1; i <= n; i++ ){
fin >> v[i].p >> v[i].t;
}
sort( v + 1, v + n + 1 );
sum = 0;
for( int i = 1; i <= n; i++ ){
q.push( v[i].p );
sum += 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] );
}
}
fout << d[T];
return 0;
}