Cod sursa(job #2718934)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 9 martie 2021 13:13:24
Problema Peste Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>

#define NMAX 50005
using namespace std;

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

struct chestie{
    int p, t;
}v[NMAX];

inline bool cmp(chestie a, chestie b){
    if(a.t == b.t)
        return a.p < b.p;
    return a.t < b.t;
}

priority_queue<int> pq;
int dp[NMAX], nrP[NMAX];

int main()
{
    int n, k, ttotal;
    fin >> n >> k >> ttotal;

    for(int i = 1; i <= n; ++i)
        fin >> v[i].p >> v[i].t;

    sort(v + 1, v + n + 1, cmp);

    int sum = 0;
    for(int i = 1; i <= n; ++i){
        sum += v[i].p;
        pq.push(-v[i].p);
        while(pq.size() > k){
            sum += pq.top();
            pq.pop();
        }

        nrP[v[i].t] = sum;
    }

    for(int i = 2; i <= 1000; ++i)
        nrP[i] = max(nrP[i], nrP[i - 1]);

    for(int i = 1; i <= ttotal; ++i){
        dp[i] = dp[i - 1];
        for(int j = 2; j <= min(i, 1000); ++j)
            dp[i] = max(dp[i], dp[i - j] + nrP[j]);
    }
    fout << dp[ttotal] << '\n';
    return 0;
}