Cod sursa(job #173806)

Utilizator devilkindSavin Tiberiu devilkind Data 8 aprilie 2008 03:54:21
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 1024
#define SMAX 50002
#define pb push_back
#define sz size()
#define mp make_pair
#define ff first
#define ss second

long long a[NMAX];
long long d[SMAX];
long int h[NMAX];
long int n,i,j,k,T,Tm,aux,cnt;
vector< pair<int, int> > v;
set<int> S;
set<int> ::iterator it;
long int x,y;

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

        scanf("%ld %ld %ld",&n,&k,&T);

        Tm=0;
        for (i=1;i<=n;i++)
                {
                scanf("%ld %ld",&x,&y);
                v.pb( mp(y,x) );
                Tm=max(y,Tm);
                }

        sort( v.begin(), v.end() );
        x=-1;
        a[0]=0;
        cnt=0;
        for (i=1;i<=Tm;i++)
                {
                a[i]=a[i-1];
                while ( (x<n-1)&&(v[x+1].ff==i) ) {
                                     x++;
                                     if (cnt < k ) {S.insert(v[x].ss);
                                                     a[i]+=v[x].ss;
                                                     h[ v[x].ss ]++;
                                                     cnt++;
                                                     continue;}

                                     if (cnt == k)
                                                {
                                                it=S.begin();
                                                if ( (*it) < v[x].ss ) {
                                                                        a[i]-=(*it);
                                                                        h[(*it)]--;
                                                                        if ( h[ (*it) ]==0 ) S.erase(it);
                                                                        a[i]+=v[x].ss;
                                                                        S.insert(v[x].ss);
                                                                        h[ v[x].ss ] ++;
                                                                       }
                                                }
                                     }
       //         printf("%ld %ld\n",i,a[i]);
                }

        d[0]=0;
        for (i=1;i<=T;i++)
                {
                d[i]=0;
                for (j=min(i,Tm);j;j--)
                       d[i]=max(d[i],d[i-j]+a[j]);
                }
        printf("%lld",d[T]);
        return 0;
}