Cod sursa(job #1958344)

Utilizator akaprosAna Kapros akapros Data 8 aprilie 2017 12:12:34
Problema Peste Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>
#define maxN 1002
#define maxT 50002
#define ll long long
using namespace std;

FILE *fin = freopen("peste.in", "r", stdin);
FILE *fout = freopen("peste.out", "w", stdout);

/* ==================== */
int n, k, totalT;
/* ==================== */
struct Net
{
    int f, t;
    bool operator < (const Net &ot) const
    {
        return t < ot.t;
    }
} v[maxN];
priority_queue < int > q;

ll dp[maxT], best[maxN];
/* ==================== */
ll ans;

void compBest()
{
    for (int i = 1; i <= n; ++ i)
    {
        int val = 0;
        q.push(-v[i].f);
        if (q.size() > k)
        {
            val = -q.top();
            q.pop();
        }
        best[i] = best[i - 1] - val + 1LL * v[i].f;
    }
}
ll compDp(int t)
{
    if (t < v[1].t)
        return 0LL;
    if (dp[t])
        return dp[t];

    for (int i = 1; v[i].t <= t; ++ i)
        dp[t] = max(dp[t], best[i] + compDp(t - v[i].t));
    return dp[t];
}

int main()
{
    scanf("%d %d %d", &n, &k, &totalT);
    for (int i = 1; i <= n; ++ i)
        scanf("%d %d", &v[i].f, &v[i].t);

    sort(v + 1, v + n + 1);
    compBest();
    ans = compDp(totalT);
    printf("%lld\n", ans);

    return 0;
}