Cod sursa(job #164738)

Utilizator filipbFilip Cristian Buruiana filipb Data 24 martie 2008 19:17:16
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

#define maxim(a, b) ((a > b) ? a : b)

int N, K, T, bst[50005], peste[1005], S;
pair<int, int> P[50005];
priority_queue<int> Q;

int main(void)
{
    int i, j, min;
    
    freopen("peste.in", "r", stdin);
    freopen("peste.out", "w", stdout);

    scanf("%d %d %d", &N, &K, &T);
    for (i = 1; i <= N; ++i)
        scanf("%d %d", &P[i].second, &P[i].first);
    sort(P+1, P+N+1);

    for (i = 1; i <= N; ++i)
    {
        if (Q.size() < K)
        {
            S += P[i].second;
            Q.push(-P[i].second);
        }
        else
        {
            min = -Q.top();
            if (min < P[i].second)
                S = S - min + P[i].second,
                Q.pop(), Q.push(-P[i].second);                
        }
        peste[P[i].first] = S;
    }

    for (i = 1; i <= 1000; ++i)
        if (!peste[i])
            peste[i] = peste[i-1];

    for (i = 1; i <= T; ++i)
        for (j = 1; j <= 1000 && j <= i; ++j)
            bst[i] = maxim(bst[i], bst[i-j] + peste[j]);

    printf("%d\n", bst[T]);
            
    return 0;
}