Cod sursa(job #1450301)

Utilizator delia_99Delia Draghici delia_99 Data 12 iunie 2015 15:19:48
Problema Peste Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cctype>
using namespace std;

const int Bsize = (1 << 16);

struct aww
{
    int fish,t;
};

int n,k,T,i,Max,s,j,p;
long long aux[1010];
long long D[50010];
aww v[50010];
char Buffer[Bsize];

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

inline bool cmp(aww A,aww B)
{
    if(A.t<B.t)
        return true;
    if(A.t==B.t && A.fish<B.fish)
        return true;
    return false;
}

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

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

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

    }
}

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(T);
    for(i=1; i<=n; ++i)
    {
        get_number(v[i].fish); get_number(v[i].t);
        if(v[i].t>Max)
            Max=v[i].t;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1; i<=n; ++i)
    {
        H.push(v[i].fish);
        s+=v[i].fish;
        if(i>k)
        {
            s-=H.top();
            H.pop();
        }
        aux[v[i].t]=s;
    }
    for(i=1; i<=Max; ++i)
        aux[i]=max(aux[i-1],aux[i]);
    for(i=1; i<=T; ++i)
        for(j=1; j<=i && j<=Max; ++j )
            D[i]=max(D[i],D[i-j]+aux[j]);
    printf("%lld\n",D[T]);
    return 0;
}