Pagini recente » Cod sursa (job #2049802) | Cod sursa (job #2877633) | Cod sursa (job #1269381) | Cod sursa (job #1765441) | Cod sursa (job #1854273)
#include <bits/stdc++.h>
using namespace std;
fstream in ( "peste.in" , ios::in );
fstream out( "peste.out", ios::out );
const int MAXT = 5e4 + 5;
const int MAXN = 1e3 + 5;
priority_queue<int, vector<int>, greater<int>> prq;
pair<int, int> arr[MAXT]; long long dp[MAXT]; int cst[MAXN];
int main() {
ios::sync_with_stdio( false );
int n, k, t;
in >> n >> k >> t;
for( int i = 1; i <= n; i ++ )
in >> arr[i].second >> arr[i].first;
sort( arr + 1, arr + n + 1 );
for( int i = 1, j = 1, s = 0; i < MAXN; i ++ ) {
while( j <= n && arr[j].first == i ) {
s += arr[j].second;
prq.push( arr[j].second );
if( prq.size() > k ) {
s -= prq.top();
prq.pop();
}
j ++;
}
cst[i] = s;
}
for( int i = 1; i <= t; i ++ ) {
for( int j = i - 1; j > max( -1, i - MAXN ); j -- )
dp[i] = max( dp[i], dp[j] + cst[i - j] );
}
out << dp[t] << endl;
return 0;
}