Cod sursa(job #1855997)

Utilizator robx12lnLinca Robert robx12ln Data 24 ianuarie 2017 13:59:07
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
#define t first
#define p second
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
int n, k, T, best[50005], sum;
long long d[50005];
pair<int,int> v[50005];
priority_queue< int, vector<int>, greater<int> > q;
int main(){
    fin >> n >> k >> T;
    for( int i = 1; i <= n; i++ ){
        fin >> v[i].p >> v[i].t;
    }
    sort( v + 1, v + n + 1 );
    sum = 0;
    for( int i = 1; i <= n; i++ ){
        q.push( v[i].p );
        sum += v[i].p;
        if( q.size() > k ){
            sum -= q.top();
            q.pop();
        }
        best[ v[i].t ] = max( best[ v[i].t ], sum );
    }
    best[0] = 0;
    for( int i = 1; i <= T; i++ ){
        best[i] = max( best[i], best[i - 1] );
    }
    d[0] = 0;
    for( int i = 1; i <= T; i++ ){
        for( int j = i - 1; j >= 0; j-- ){
            d[i] = max( d[i], d[j] + 1LL * best[i - j] );
        }
    }
    fout << d[T];
    return 0;
}