Cod sursa(job #2097863)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 1 ianuarie 2018 19:22:35
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = (int) 5e4;
const int MAXT = (int) 1e3;

pair <int, int> v[MAXN + 1];

int best[MAXT + 1];

multiset <int> mst;

int dp[MAXN + 1];

int main() {
    ifstream cin("peste.in");
    ofstream cout("peste.out");
    int i, n, k, total, j;
    ios::sync_with_stdio(false);
    cin >> n >> k >> total;
    for(i = 1; i <= n; i++) {
        cin >> v[i].second >> v[i].first;
    }
    sort(v + 1, v + n + 1);
    int p = 1;
    int sum = 0;
    for(i = 1; i <= MAXT; i++) {
        while(p <= n && v[p].first <= i) {
            if(mst.size() < k) {
                mst.insert(v[p].second);
                sum += v[p].second;
            }
            else if(v[p].second > *mst.begin()) {
                sum += v[p].second - *mst.begin();
                mst.erase(mst.begin());
                mst.insert(v[p].second);
            }
            p++;
        }
        best[i] = sum;
    }
    for(i = 1; i <= total; i++) {
        for(j = 1; j <= min(i, MAXT); j++) {
            dp[i] = max(dp[i], dp[i - j] + best[j]);
        }
    }
    cout << dp[total];
    cin.close();
    cout.close();
    return 0;
}