Cod sursa(job #1450017)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 11 iunie 2015 10:31:45
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <algorithm>
#include <set>

#define timp first
#define plasa second

#define ll long long

using namespace std;

const int Nmax = 50010;

int n , k , total , i , limita , j;

ll sum;
ll maxim[Nmax] , ans[Nmax];

pair < int , int > A[Nmax];

multiset < int > S;

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

    scanf("%d %d %d", &n, &k, &total);

    for (i = 1; i <= n; ++i)
    {
        scanf("%d %d", &A[i].plasa, &A[i].timp);
        limita = max(limita , A[i].timp);
    }

    sort(A + 1 , A + n + 1);

    for (j = 1, i = 1; i <= limita; ++i)
    {
        for ( ; j <= n && A[j].timp <= i; ++j)
            S.insert(A[j].plasa),
            sum += 1LL * A[j].plasa;

        for ( ; S.size() > k; sum -= *S.begin(), S.erase(S.begin()));

        maxim[i] = 1LL * sum;
    }

    for (i = 1; i <= total; ++i)
     for (j = 1; j <= min(i , limita); ++j)
        ans[i] = max(ans[i] , ans[i-j] + maxim[j]);

    printf("%lld\n", ans[total]);

    return 0;
}