Cod sursa(job #485508)

Utilizator cont_de_testeCont Teste cont_de_teste Data 18 septembrie 2010 16:43:03
Problema Peste Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
# include <algorithm>
# include <queue>
using namespace std;

# define x first
# define y second

typedef long long ll ;
const char FIN[] = "peste.in", FOU[] = "peste.out" ;
const int MAX_N = 50005, MAX_T = 1005 ;

priority_queue < short > Q ;
pair < int, int > V[MAX_N] ;
ll S[MAX_N], sol ;
int H[MAX_T] ;
int N, K, TT ;

int main ( void ) {
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "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 ) ;

    return 0 ;
}