Cod sursa(job #2337074)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 5 februarie 2019 21:03:28
Problema Peste Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <cstdio>
#include <set>
#include <vector>

using namespace std;

const int VAL=50005;
const int TMAX=1005;


int N, K, TOT, i, j, mx;
int P, T, SUM, nr[VAL];
long long dp[VAL];
multiset <int> Heap;
multiset <int> :: iterator it;
vector <int> V[TMAX];

int main()
{
    freopen("peste.in", "r", stdin);
    freopen("peste.out", "w", stdout);
    scanf("%d %d %d", &N, &K, &TOT);
    for (i=1; i<=N; i++)
    {
        scanf("%d %d", &P, &T);
        mx=max(mx, T);
        V[T].push_back(P);
    }
    for (i=1; i<=mx; i++)
    {
        for (j=0; j<V[i].size(); j++)
        {
            if (Heap.size()<K)
            {
                Heap.insert(V[i][j]);
                SUM+=V[i][j];
                continue;
            }
            it=Heap.begin();
            if (*it<V[i][j])
            {
                SUM-=*it;
                Heap.erase(it);
                Heap.insert(V[i][j]);
                SUM+=V[i][j];
            }
        }
        nr[i]=SUM;
    }
    for (i=1; i<=TOT; i++)
        for (j=max(0, i-mx); j<i; j++)
            dp[i]=max(dp[i], dp[j]+nr[i-j]);
    printf("%lld\n", dp[TOT]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}