Cod sursa(job #2040241)

Utilizator osiaccrCristian Osiac osiaccr Data 15 octombrie 2017 15:36:44
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <queue>
#include <algorithm>
#define DEF 50005

using namespace std;

ifstream fin ("peste.in");
ofstream fout ("peste.out");

int n, k, TMAX;
long long s, aux[DEF], best[DEF];

pair < int, int > v[DEF];

priority_queue < int, vector < int >, greater < int > > H;

int main () {
    fin >> n >> k >> TMAX;
    for (int i = 1; i <= n; i++) {
        fin >> v[i].second >> v[i].first;
    }
    sort (v + 1, v + n + 1);

    for (int i = 1; i <= n; i++) {
        H.push (v[i].second);
        s += v[i].second;
        while (H.size () > k) {
            s -= H.top ();
            H.pop ();
        }
        aux[v[i].first] = max (s, aux[v[i].first]);
    }

    for (int i = 1; i <= TMAX; i++) {
        for (int j = 0; j <= min (i, v[n].first); j++) {
            best[i] = max (best[i], best[i - j] + aux[j]);
        }
    }

    fout << best[TMAX];

    return 0;
}