Cod sursa(job #204623)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 25 august 2008 18:27:41
Problema Peste Scor 40
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];

struct comp   
{  
    bool operator () (int x,int y) const  
    { return V[x].p < V[y].p; }  
};  
multiset<int, comp > M;

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

void solve()
{
	int ki,k(1);
	
	FOR(i,1,Ttotal)
	{
		while(V[k].t <= i && k<=N)
			M.insert(k),
			++k;
		multiset<int, comp >::iterator it;
		
		ki = M.size() - K; 
		for(it = M.begin(); it != M.end() && ki>0;++it)
			M.erase(it),--ki;
		
		for(it = M.begin(); it != M.end();++it)
			A[i] += V[*it].p;
		
	}	
	
	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;
}