Cod sursa(job #485507)

Utilizator cont_de_testeCont Teste cont_de_teste Data 18 septembrie 2010 16:40:03
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <queue>
#include <algorithm>

using namespace std;

#define x first
#define y second
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define FORi(i,s,d) for(i=(s);i<(d);++i, H[i] = H[i-1])
#define nmax 50005
#define tmax 1005

typedef long long lint;

priority_queue <short> Q;
pair <int,int> P[nmax];
int n,k,T,H[tmax];
lint A[nmax],sol;

int main()
{
	int i,j;
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	scanf("%d %d %d",&n,&k,&T);
	for ( int i = 0; i < n; ++i ) {
        scanf ( "%d %d", &P[i].y, &P[i].x ) ;
    }
	sort(P,P+n);
    for ( int i = 0, j = 1, l = 0; j <= 1000; ++j, H[j] = H[j - 1] )
	{
		for ( ; i < n && P[i].x == j ; Q.push ( -P[i].y ) , ++l, H[j] += P[i++].y ) ;
        for ( ; k < l ; H[j] += Q.top () , Q.pop (), --l ) ;
	}
	for ( int i = 0; i <= T; ++i ) {
        if ( sol < A[i] ) {
            sol = A[i] ;
        }
        for ( int j = 1; j <= 1000; ++j ) {
            if ( A[i + j] < A[i] + H[j] ) {
                A[i + j] = A[i] + H[j] ;
            }
        }
    }
	printf("%lld",sol);
	return 0;
}