Pagini recente » Cod sursa (job #491064) | Cod sursa (job #2617666) | Cod sursa (job #2381138) | Cod sursa (job #1687035) | Cod sursa (job #1915104)
#include <fstream>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream in("peste.in");
ofstream out("peste.out");
typedef long long I64;
const int NMAX = 50005;
const int TMAX = 1001;
struct TIP {
int p, t;
};
TIP P[NMAX + 4];
int aux[TMAX + 4];
I64 d[NMAX + 4];
int N, K, T;
priority_queue < int, vector <int>, greater<int> > H;
bool cmp( const TIP& a, const TIP& b ) {
if( a.t == b.t ) return a.p < b.p;
return a.t < b.t;
}
int main()
{
in >> N >> K >> T;
for( int i = 1; i <= N; ++i ) {
in >> P[i].p >> P[i].t;
}
int s = 0;
sort( P+1, P+N+1, cmp );
for( int i = 1; i <= N; ++i ) {
H.push( P[i].p );
s += P[i].p;
if(i > K) {
s -= H.top();
H.pop();
}
aux[P[i].t] = s;
}
for( int i = 1; i <= TMAX; ++i ) {
aux[i] = max( aux[i - 1], aux[i] );
}
for( int i = 1; i <= T; ++i ) {
for( int j = 1; j <= TMAX && j <= i; ++j ) {
if( d[i - j] + aux[j] > d[i] ) {
d[i] = d[i - j] + aux[j];
}
}
}
out << d[T] << '\n';
return 0;
}