Pagini recente » Cod sursa (job #3282452) | Cod sursa (job #2555546) | Cod sursa (job #3284400) | Cod sursa (job #1187661) | Cod sursa (job #160830)
Cod sursa(job #160830)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAX_TIMP 50010
#define MAX_N 50010
#define MAX_T 1010
#define llong long long
#define pb push_back
#define mp make_pair
#define PII pair<int, int>
#define x first
#define y second
int N, K, T; llong best[MAX_TIMP], fish[MAX_T];
vector< int > G[MAX_T];
priority_queue<int> Q;
void solve(void)
{
int i, t, j, k; vector<int>::iterator it;
for(t = 1; t < MAX_T; t++)
{
fish[t] = fish[t-1];
for(i = 0, it = G[t].begin(); it != G[t].end(); i++, ++it)
{
if( Q.size() < K ) { fish[t] += (llong)*it, Q.push(-(*it));
continue ; }
if( Q.size() == K && -Q.top() < *it )
fish[t] -= (llong)-Q.top(), Q.pop(), Q.push(-(*it)),
fish[t] += (llong)*it;
}
}
for(t = 1; t <= T; t++)
for(best[t] = best[t-1], i = 1; i <= t && i < MAX_T; i++)
best[t] = max(best[t], best[t-i]+fish[i]);
}
void read_data(void)
{
int i, j, k;
scanf("%d %d %d\n", &N, &K, &T);
for(i = 1; i <= N; i++) scanf("%d %d", &j, &k), G[k].pb(j);
}
void write_data(void)
{
printf("%lld\n", best[T]);
}
int main(void)
{
freopen("peste.in", "rt", stdin);
freopen("peste.out", "wt", stdout);
read_data();
solve();
write_data();
fprintf(stderr, "%lld\n", best[T]);
return 0;
}