Cod sursa(job #904162)

Utilizator danalex97Dan H Alexandru danalex97 Data 3 martie 2013 20:15:52
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define F stdin

const int Buffer=1<<13;
char Buff[Buffer]; int Next=0;

int get_int()
{
    int Nbr=0;
    while( Buff[Next]<'0' || '9'<Buff[Next] )
        if ( ++Next >= Buffer ) fread(Buff,Buffer,1,F), Next=0;
    while ( '0'<=Buff[Next] && Buff[Next]<='9' )
    {
        Nbr=Nbr*10+Buff[Next]-'0';
        if ( ++Next >= Buffer ) fread(Buff,Buffer,1,F), Next=0;
    }
    return Nbr;
}

#define maxn 50010
#define maxt 1010
#define ll long long

int n, k, m, nr;
int a[maxn], b[maxn], p[maxn];
ll c[maxn];
int best[maxt], v[maxt];

inline int cmp(int x, int y)
{ return b[x] < b[y]; }

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

    n=get_int();
    k=get_int();
    m=get_int();

    int i, j, x;

    for (i=1; i<=n; i++)
    {
        a[i]=get_int();
        b[i]=get_int();
        p[i] = i;
    }

    sort(p+1, p+n+1, cmp);

    j = x = 1;

    for (i=1; i<maxt; i++)
    {
        best[i] = best[i-1];

        for (; b[p[j]] == i; j++)
            if (a[p[j]] >= x)
            {
                nr++;
                best[i] += a[p[j]];
                v[a[p[j]]]++;
            }

        for (; x<maxt && nr>k; )
            if (v[x])
            {
                best[i] -= x;
                v[x]--, nr--;
            }
            else x++;
    }

    for (i=0; i<=m; i++)
        for (j=1; j<maxt && i+j<=m; j++) c[i+j] = max(c[i+j], c[i] + best[j]);

    printf("%lld\n", c[m]);

    return 0;
}