Cod sursa(job #1157387)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 28 martie 2014 14:43:42
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <cstring>

#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
 using namespace std;
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;
}