Pagini recente » Cod sursa (job #615847) | Cod sursa (job #597431) | Cod sursa (job #2137300) | Cod sursa (job #2705831) | Cod sursa (job #485511)
Cod sursa(job #485511)
#include <queue>
#include <algorithm>
using namespace std;
#define x first
#define y second
#define nmax 50005
#define tmax 1005
typedef long long lint;
priority_queue < short > Q ;
pair < int, int > P[nmax] ;
int n,k,T,H[tmax];
lint A[nmax],sol;
int main()
{
int i,j;
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d %d %d",&n,&k,&T);
for ( int i = 0; i < n; ++i ) {
scanf ( "%d %d", &P[i].y, &P[i].x ) ;
}
sort(P,P+n);
for ( int i = 0, j = 1, l = 0; j <= 1000; ++j, H[j] = H[j - 1] )
{
for ( ; i < n && P[i].x == j ; Q.push ( -P[i].y ) , ++l, H[j] += P[i++].y ) ;
for ( ; k < l ; H[j] += Q.top () , Q.pop (), --l ) ;
}
for ( int i = 0; i <= T; ++i ) {
if ( sol < A[i] ) {
sol = A[i] ;
}
for ( int j = 1; j <= 1000; ++j ) {
if ( A[i + j] < A[i] + H[j] ) {
A[i + j] = A[i] + H[j] ;
}
}
}
printf ( "%lld", sol ) ;
}