Mai intai trebuie sa te autentifici.
Cod sursa(job #1958391)
Utilizator | Data | 8 aprilie 2017 12:48:19 | |
---|---|---|---|
Problema | Peste | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.38 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
{
if (t == ot.t)
return f < ot.f;
return t < ot.t;
}
} v[maxN];
priority_queue < int > q;
ll dp[maxT], best[maxN];
bool vis[maxT];
/* ==================== */
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 (vis[t])
return dp[t];
for (int i = 1; i <= n && v[i].t <= t; ++ i)
if (v[i].t != v[i + 1].t || i == n)
dp[t] = max(dp[t], best[i] + compDp(t - v[i].t));
vis[t] = 1;
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;
}