Cod sursa(job #2040052)

Utilizator osiaccrCristian Osiac osiaccr Data 15 octombrie 2017 13:09:34
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <set>
#include <algorithm>
#define DEF 50001

using namespace std;

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

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

pair < int, int > v[DEF];

multiset < pair < int, int > > S;

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 <= tmax; i++) {
        while (v[_i].first <= i && _i <= n) {
            S.insert (make_pair ((-1) * v[_i].second, v[_i].first));
            _i++;
        }
        _j = 0;
        for (multiset < pair < int, int > >::iterator it = S.begin (); it != S.end () && _j < k; it++, _j++) {
            aux[i] += (-1) * (it -> first);
        }
    }

    for (int i = 1; i <= TMAX; i++) {
        for (int j = 1; j <= i; j++) {
            best[i] = max (best[i], best[i - j] + aux[j]);
        }
    }

    fout << best[TMAX];

    return 0;
}