Cod sursa(job #204640)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 25 august 2008 18:51:34
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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
#define ll long long

int TM,N,K,Ttotal;
vector< pair<int,int> > V(N_MAX);
ll 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);
			ok=true;
			A[i] += V[k].p;
			++k;
		}	
			
		A[i] += A[i-1];
		if(!ok)
			continue;
				
		multiset<int>::iterator it;
		
		ki = M.size() - K;
		if(ki < 0)
			continue;
		for(it = M.begin(); it != M.end() && ki>0;++it)
		{
			A[i] -= *it;
			M.erase(it),--ki;
		}	
	}	
	
	FOR(i,0,Ttotal)
		for(int j=i-1;j>= max(0,i-TM);--j)
			if( S[i] < S[j] + A[i-j])
				S[i] = S[j] + A[i-j];
	
	printf("%lld\n", S[Ttotal]);	
}

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