Cod sursa(job #1675344)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 5 aprilie 2016 11:42:18
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

const int UNDEF = -1;

int n, k, t;
pair<int, int> v[50002];
long long maxp[50002], din[50002];
vector<int> pq;

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

    fin >> n >> k >> t;
    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 <= 50000; ++i)
        maxp[i] = UNDEF;

    long long ind = 1, sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        pq.push_back(v[i].second);
        push_heap(pq.begin(), pq.end(), greater<int>());

        sum += v[i].second;

        if (pq.size() > k)
        {
            sum -= pq.front();
            pop_heap(pq.begin(), pq.end(), greater<int>());
            pq.pop_back();
        }

        maxp[v[i].first] = max(maxp[i], sum);
    }

    long long last = 0;
    for (int i = 1; i <= 1000; ++i)
    {
        maxp[i] = max(maxp[i], last);
        last = maxp[i];
    }

    for (int i = 1; i <= t; ++i)
        for (int j = i - 1; j >= max(i - 1000, 0); --j)
            din[i] = max(din[i], din[j] + maxp[i - j]);

    fout << din[t];

    fin.close();
    fout.close();
}