Cod sursa(job #3194592)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 18 ianuarie 2024 18:36:22
Problema Peste Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

const int max_size = 5e4 + 20, max_dp = 1e3 + 20;

struct str{
    int x;
    bool operator < (const str & aux) const
    {
        return x > aux.x;
    }
};

pair <int, int> psc[max_size];
int dp[max_size], best[max_dp];
priority_queue <str> pq;

bool cmp (pair <int, int> x, pair <int, int> y)
{
    return x.second < y.second;
}

void solve ()
{
    int n, k, tt;
    cin >> n >> k >> tt;
    for (int i = 1; i <= n; i++)
    {
        cin >> psc[i].first >> psc[i].second;
    }
    sort(psc + 1, psc + n + 1, cmp);
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += psc[i].first;
        pq.push({psc[i].first});
        if (i > k)
        {
            sum -= pq.top().x;
            pq.pop();
        }
        best[psc[i].second] = sum;
    }
    for (int i = 1; i <= 1000; i++)
    {
        best[i] = max(best[i], best[i - 1]);
    }
    for (int i = 1; i <= tt; i++)
    {
        for (int j = 1; j <= min(i, 1000); j++)
        {
            dp[i] = max(dp[i], dp[i - j] + best[j]);
        }
    }
    cout << dp[tt];
    cout << '\n';
}

signed main ()
{
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    freopen("peste.in", "r", stdin);
    freopen("peste.out", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long t;
    //cin >> t;
    t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}