Pagini recente » Cod sursa (job #48899) | Cod sursa (job #152744) | Cod sursa (job #1315084) | Cod sursa (job #1454163) | Cod sursa (job #3194592)
#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;
}