Cod sursa(job #204636)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 25 august 2008 18:39:23
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
using namespace std;

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <utility>

#define IN "peste.in"
#define OUT "peste.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<16
#define t first
#define p second

int TM,N,K,Ttotal;
vector< pair<int,int> > V(N_MAX);
int A[N_MAX],S[N_MAX];

multiset<int> M;

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d %d %d\n",&N,&K,&Ttotal);
	V.resize(N);	
	FOR(i,1,N)
	{
		scanf("%d%d", &V[i].p,&V[i].t);
		TM = max(V[i].t,TM);
	}
	sort(V.begin(), V.end() );	
}

void solve()
{
	int ki,k(1);
	bool ok(0);
	
	FOR(i,1,Ttotal)
	{
		ok = false;
		while(V[k].t <= i && k<=N)
			M.insert(V[k].p),
			++k,ok=true;
		if(!ok)
		{
			A[i] = A[i-1];
			continue;
		}
		
		multiset<int>::iterator it;
		
		ki = M.size() - K;
		if(ki > 0)
		{
			for(it = M.begin(); it != M.end() && ki>0;++it)
				M.erase(it),--ki;
		}	
		
		for(it = M.begin(); it != M.end();++it)
			A[i] += *it;
	}	
	
	FOR(i,0,Ttotal)
		for(int j=i-1;j>= max(0,i-TM);--j)
			S[i] = max(S[i], S[j] + A[i-j]);
	
	printf("%d\n", S[Ttotal]);	
}

int main()
{
	scan();
	solve();
	return 0;
}