Cod sursa(job #2823610)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 29 decembrie 2021 00:25:19
Problema Peste Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

#pragma GCC optimize ("Ofast")

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

struct heapInt {
    int val;
    inline bool operator < (const heapInt &other) const
    {
        return val > other.val;
    }
};

struct plasa {
    int p, t;
}v[50'005];

int n, sum, pst[50'005], k, timp;
long long dp[50'005];
priority_queue <heapInt> heap;

bool cmp(plasa a, plasa b)
{
    return a.t < b.t;
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin >> n >> k >> timp;
    for(int i = 1; i <= n; i++)
        fin >> v[i].p >> v[i].t;
    sort(v + 1, v + n + 1, cmp);
    for(int i = 1; i <= n; i++)
    {
        sum = sum + v[i].p;
        heap.push({v[i].p});
        if(i > k)
        {
            sum = sum - heap.top().val;
            heap.pop();
        }
        pst[v[i].t] = sum;
    }
    for(int i = 1; i <= 1000; i++)
        pst[i] = max(pst[i], pst[i - 1]);
    for(int i = 1; i <= timp; i++)
    {
        dp[i] = dp[i - 1];
        for(int j = 1; j <= min(i, 1000); j++)
            dp[i] = max(dp[i], dp[i - j] + pst[j]);
    }
    fout << dp[timp] << '\n';
    return 0;
}