Cod sursa(job #1744952)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 20 august 2016 19:18:21
Problema Peste Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

ifstream cin("peste.in");
ofstream cout("peste.out");

const int MAXN = 50005;
const int MAXT = 1002;

struct Fishnet {
    int p;
    int t;
};

Fishnet v[MAXN];
int sum[MAXT];
long long dp[MAXN];

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

bool Compare(const Fishnet &a, const Fishnet &b) {
    if (a.t == b.t)
        return a.p < b.p;
    return a.t < b.t;
}

int main() {
    int n, k, t, big = 0;
    cin >> n >> k >> t;
    for (int i = 1; i <= n; i++) {
        cin >> v[i].p >> v[i].t;
        if (v[i].t > big)
            big = v[i].t;
    }
    sort(v + 1, v + n + 1, Compare);
    int value = 0;
    for (int i = 1; i <= n; i++) {
        Heap.push(v[i].p);
        value += v[i].p;
        if (i > k) {
            value -= Heap.top();
            Heap.pop();
        }
        sum[v[i].t] = value;
    }
    for (int i = 1; i <= big; i++)
        sum[i] = max(sum[i], sum[i - 1]);
    for (int i = 1; i <= t; i++)
        for (int j = 1; j <= big && j <= i; j++)
            if (dp[i - j] + sum[j] > dp[i])
                dp[i] = dp[i - j] + sum[j];
    cout << dp[t];
    return 0;
}