Pagini recente » Cod sursa (job #1206074) | Cod sursa (job #2269716) | Cod sursa (job #1271258) | Cod sursa (job #1523488) | Cod sursa (job #487679)
Cod sursa(job #487679)
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
struct vect
{
int t, p;
};
int n, k, t;
vect v[50002];
int nr[1002], sol[50002];
priority_queue <int, vector <int>, greater <int> > heap;
inline int cmp (vect a, vect b)
{
return a.t < b.t;
}
inline int max (int a, int b) {return a > b ? a : b;}
int main ()
{
freopen ("peste.in", "r", stdin);
freopen ("peste.out", "w", stdout);
scanf ("%d %d %d", &n, &k, &t);
int i, j, s = 0;
for (i = 1; i <= n; i ++)
scanf ("%d %d", &v[i].p, &v[i].t);
sort (v + 1, v + n + 1, cmp);
for (i = 1; i <= n; i ++)
{
s += v[i].p;
heap.push (v[i].p);
if (heap.size() > k)
{
s -= heap.top ();
heap.pop ();
}
nr[v[i].t] = max (nr[i], s);
}
for (i = 1; i <= 1000; i ++)
nr[i] = max (nr[i], nr[i - 1]);
for (i = 1; i <= t; i ++)
for (j = i - 1; j >= max (i - 1000, 0); j --)
sol[i] = max (sol[i], sol[j] + nr[i - j]);
printf ("%d\n", sol[t]);
return 0;
}