Pagini recente » Cod sursa (job #1276501) | Cod sursa (job #974151) | Cod sursa (job #1051428) | Cod sursa (job #1139066) | Cod sursa (job #487678)
Cod sursa(job #487678)
#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 ++)
{
for (j = v[i - 1].t + 1; j < v[i].t; j ++)
nr[j] = max (nr[j - 1], s);
s += v[i].p;
heap.push (v[i].p);
if (heap.size() > k)
{
s -= heap.top ();
heap.pop ();
}
nr[j] = max (nr[j - 1], 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;
}