Pagini recente » Cod sursa (job #2257079) | Cod sursa (job #2912071) | Cod sursa (job #832740) | Cod sursa (job #2990789) | Cod sursa (job #163564)
Cod sursa(job #163564)
#include <stdio.h>
#include <string.h>
#define LL long long
#define FOR(i, a, b) for (int (i) = (a); (i) < (int)(b); ++(i))
#define MAXT 50005
#define MAXN 50005
#define MAXV 1000
int N, K, TIME;
int P[MAXN], T[MAXN];
LL maxP[MAXN];
int used[MAXV + 5];
LL bst[MAXT];
int main()
{
freopen("peste.in", "rt", stdin);
freopen("peste.out", "wt", stdout);
scanf("%d %d %d", &N, &K, &TIME);
FOR(i, 0, N)
scanf("%d %d", P + i, T + i);
FOR(i, 1, MAXV + 1)
{
memset( used, 0, sizeof(used) );
maxP[i] = 0;
FOR(j, 0, N)
if (T[j] <= i)
used[ P[j] ]++;
int left = K;
for (int k = MAXV; k >= 1 && left; k--)
{
if (!used[k])
continue;
if (used[k] <= left)
maxP[i] += (long long)k * (long long)used[k],
left -= used[k];
else
maxP[i] += (long long)k * (long long)left,
left = 0;
}
}
bst[0] = 0;
FOR(i, 1, TIME + 1)
{
bst[i] = -1;
FOR(k, 1, MAXV + 1)
{
if (k > i)
break;
if (bst[i - k] + maxP[k] > bst[i])
bst[i] = bst[i - k] + maxP[k];
}
}
printf("%lld\n", bst[TIME]);
return 0;
}