Cod sursa(job #485503)

Utilizator cont_de_testeCont Teste cont_de_teste Data 18 septembrie 2010 16:35:16
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 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,l;
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	scanf("%d %d %d",&n,&k,&T);
	FOR(i,0,n)
	{
		scanf("%d %d",&P[i].y,&P[i].x);
	}
	sort(P,P+n);
	i=l=0;
	FORi(j,1,1001)
	{
		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(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",sol);
	return 0;
}