Cod sursa(job #160824)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 16 martie 2008 22:58:34
Problema Peste Scor Ascuns
Compilator cpp Status done
Runda Marime 0.96 kb
#include <stdio.h>
#include <assert.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

#define f first
#define s second
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define nmax 65536
#define tmax 1024

typedef long long lint;

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

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