Cod sursa(job #2040237)

Utilizator osiaccrCristian Osiac osiaccr Data 15 octombrie 2017 15:29:25
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <queue>
#include <algorithm>
#define DEF 50001

using namespace std;

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

int n, k, TMAX, _i = 1, s, aux[DEF], best[DEF], tmax;

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;
        tmax = max (tmax, 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 = 1; j <= min (i, v[n].first); j++) {
            best[i] = max (best[i], best[i - j] + aux[j]);
        }
    }

    fout << best[TMAX];

    return 0;
}