Pagini recente » Cod sursa (job #309056) | Monitorul de evaluare | Clasament dupa rating | Clasament dupa rating | Cod sursa (job #485514)
Cod sursa(job #485514)
#include <algorithm>
#include <queue>
using namespace std;
#define x first
#define y second
typedef long long ll;
const int nmax = 50005, tmax = 1005 ;
priority_queue < short > Q ;
pair < int, int > V[nmax] ;
int N,K,TT,H[tmax];
ll S[nmax],sol;
int main()
{
int i,j;
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf ( "%d %d %d", &N, &K, &TT ) ;
for ( int i = 0; i < N; ++i ) {
scanf ( "%d %d", &V[i].y, &V[i].x ) ;
}
sort(V,V + N);
for ( int i = 0, j = 1, k = 0; j <= 1000; ++j, H[j] = H[j - 1] )
{
for ( ; i < N && V[i].x == j ; Q.push ( -V[i].y ) , ++k, H[j] += V[i++].y ) ;
for ( ; K < k ; H[j] += Q.top () , Q.pop (), --k ) ;
}
for ( int i = 0; i <= TT; ++i ) {
if ( sol < S[i] ) {
sol = S[i] ;
}
for ( int j = 1; j <= 1000; ++j ) {
if ( S[i + j] < S[i] + H[j] ) {
S[i + j] = S[i] + H[j] ;
}
}
}
printf ( "%lld", sol ) ;
}