Cod sursa(job #489173)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 1 octombrie 2010 16:48:04
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#include <algorithm>
#include <set>
#define Nmax 50002
#define Tmax 1002
#define LL long long

using namespace std;

LL din[Nmax],Sp[Nmax];
struct plasa { int t,p; } P[Nmax];
int N,K,TT;
multiset< int > Set;

inline LL Maxim(LL x,LL y){ return x>y ? x:y; }
inline LL Minim(LL x,LL y){ return x<y ? x:y; }
inline int cmp(plasa a, plasa b){
	return a.t < b.t || (a.t==b.t && a.p<b.p);
}

int main(){
	int i,j,tmx,wh;
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	scanf("%d%d%d",&N,&K,&TT);
	for(i=1;i<=N;++i) scanf("%d%d",&P[i].p,&P[i].t);
	sort(P+1,P+N+1,cmp);
	tmx=P[N].t;
	
	wh=1;
	for(i=1;i<=tmx;++i){ 
		Sp[i]=Sp[i-1];
		while( P[wh].t <= i && wh<=N ){
			Set.insert(P[wh].p);
			Sp[i] += P[wh].p;
			++wh;
		}
		
		while( Set.size() > K ){
			Sp[i]=Sp[i]-*Set.begin();
			Set.erase(Set.begin());
		}
	}
	
	for(i=P[1].t;i<=TT;++i){
		din[i]=din[i-1];
		for(j=1;j<=Minim(i,tmx);++j)
			din[i]=Maxim(din[i],din[i-j]+Sp[j]);
	}
	
	printf("%lld\n",din[TT]);
	fclose(stdin); fclose(stdout);
	return 0;
}