Cod sursa(job #1856007)

Utilizator robx12lnLinca Robert robx12ln Data 24 ianuarie 2017 14:04:51
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define t first
#define p second
using namespace std;
FILE * fin = fopen("peste.in", "%r");
FILE * fout = fopen("peste.out", "%w");
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(){
    fscanf( fin, "%d%d%d", &n, &k, &T );
    for( int i = 1; i <= n; i++ ){
        fscanf( fin, "%d%d", &v[i].p, &v[i].t );
    }
    sort( v + 1, v + n + 1 );
    sum = 0;
    for( int i = 1; i <= n; i++ ){
        if( q.empty() || v[i].p > q.top() ){
            q.push( v[i].p );
            sum += v[i].p;
            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] );
        }
    }
    fprintf( fout, "%lld", d[T] );
    return 0;
}