Cod sursa(job #1450041)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 11 iunie 2015 11:23:09
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cctype>

#define timp first
#define plasa second

#define ll long long

using namespace std;

const int Nmax = 50010;
const int Tmax = 1010;
const int Bsize = (1 << 16);

int n , k , total , i , limita , j , p;
int maxim[Tmax];

ll sum;
ll ans[Nmax];

pair < int , int > A[Nmax];

priority_queue < int , vector < int > , greater < int > > S;

char Buffer[Bsize];

void get_number(int &x)
{
    x = 0;

    while (!isdigit(Buffer[p]))
        if (p < Bsize - 1)
            ++p;
        else
        {
            fread(Buffer , 1 , Bsize , stdin);
            p = 0;
        }

    while (isdigit(Buffer[p]))
    {
        x = x * 10 + Buffer[p] - '0';
        if (p < Bsize - 1)
            ++p;
        else
        {
            fread(Buffer , 1 , Bsize , stdin);
            p = 0;
        }
    }
}

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

    fread(Buffer , 1 , Bsize , stdin); p = 0;

    get_number(n); get_number(k); get_number(total);

    for (i = 1; i <= n; ++i)
    {
        get_number(A[i].plasa); get_number(A[i].timp);
        limita = max(limita , A[i].timp);
    }

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

    for (i = 1; i <= n; ++i)
    {
        S.push(A[i].plasa); sum += 1LL * A[i].plasa;

        if (i > k)
            sum -= S.top(),
            S.pop();

        maxim[A[i].timp] = 1LL * sum;
    }

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

    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;
}