Cod sursa(job #1854273)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 22 ianuarie 2017 15:45:54
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#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;
}