Pagini recente » Cod sursa (job #2710079) | Cod sursa (job #2423087) | Cod sursa (job #240868) | Cod sursa (job #1087095) | Cod sursa (job #177995)
Cod sursa(job #177995)
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
long i, j, o, t, k, n, sum, aux[1024], kn[50010];
multiset <long> h;
struct lol
{
long a, b;
};
lol x[50010];
int cmpf(lol a, lol b)
{
if (a.b != b.b)
return a.b < b.b;
return a.a > b.a;
}
int main()
{
freopen ("peste.in", "rt", stdin);
freopen ("peste.out", "wt", stdout);
scanf("%ld %ld %ld", &n, &k, &t);
for (i = 1; i <= n; ++i)
scanf("%ld %ld", &x[i].a, &x[i].b);
sort(x + 1, x + n + 1, cmpf);
sum = 0;
j = 1;
for (i = 1; i <= 1000; ++i)
{
for (; j <= n && x[j].b == i; ++j)
{
if (h.size() < k)
sum += x[j].a, h.insert(x[j].a);
else
if (x[j].a >= *h.begin())
sum -= *h.begin(), h.erase(h.begin()), h.insert(x[j].a), sum += x[j].a;
}
aux[i] = sum;
}
o = 1000 < t ? 1000 : t;
for (i = 1; i <= o; ++i)
{
if (kn[i] < aux[i])
kn[i] = aux[i];
for (j = 1; j <= t; ++j)
if (kn[j] && j + i <= t)
{
if (kn[j + i] < kn[j] + aux[i])
kn[j + i] = kn[j] + aux[i];
}
}
i = t;
while (!kn[i] && i)
--i;
printf("%ld\n", kn[i]);
return 0;
}