Cod sursa(job #160452)

Utilizator astronomyAirinei Adrian astronomy Data 15 martie 2008 21:29:04
Problema Peste Scor Ascuns
Compilator cpp Status done
Runda Marime 1.49 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define MAX_TIMP 50010
#define MAX_N 50010
#define MAX_T 1010
#define llong long long
#define pb push_back
#define mp make_pair
#define PII pair<int, int>
#define x first
#define y second


int N, K, T; llong best[MAX_TIMP], fish[MAX_T];
vector< int > G[MAX_T];
priority_queue<int> Q;

void solve(void)
{
    int i, t, j, k; vector<int>::iterator it;
    
    for(t = 1; t < MAX_T; t++)
    {
        fish[t] = fish[t-1];
        for(i = 0, it = G[t].begin(); it != G[t].end(); i++, ++it)
        {
            if( Q.size() < K ) fish[t] += (llong)*it, Q.push(-(*it));
            if( Q.size() == K && -Q.top() < *it )
                fish[t] -= (llong)-Q.top(), Q.pop(), Q.push(-(*it)),
                fish[t] += (llong)*it;
        }
    }
    for(t = 1; t <= T; t++)
     for(best[t] = best[t-1], i = 1; i <= t && i < MAX_T; i++)
        best[t] = max(best[t], best[t-i]+fish[i]);
}

void read_data(void)
{
    int i, j, k;

    scanf("%d %d %d\n", &N, &K, &T);

    for(i = 1; i <= N; i++) scanf("%d %d", &j, &k), G[k].pb(j);
}

void write_data(void)
{
    printf("%lld\n", best[T]);
}

int main(void)
{
    freopen("peste.in", "rt", stdin);
    freopen("peste.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    fprintf(stderr, "%lld\n", best[T]);
    
    return 0;
}