Cod sursa(job #532049)

Utilizator swift90Ionut Bogdanescu swift90 Data 10 februarie 2011 19:19:07
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue <long long,vector<long long>, greater<long long> > H;
struct peste{
	long long p,t;
}pes[50100];
long long pp[1100],s[50100],su;
struct cmp{
	bool operator()(const peste a,const peste b)const{
		if(a.t<b.t)
			return true;
		return false;
	}
};
int main(){
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	int N,K,T,i,j,tmp=0;
	scanf("%d%d%d",&N,&K,&T);
	for(i=0;i<N;++i)
		scanf("%lld%lld",&pes[i].p,&pes[i].t);
	sort(pes,pes+N,cmp());
	j=1;
	for(i=0;i<N;){
		tmp=pes[i].t;
		for(;j<tmp;++j)
			pp[j]=su;
		while(pes[i].t==tmp){
			su+=pes[i].p;
			H.push(pes[i].p);
			if(H.size()>K){
				su-=H.top();
				H.pop();
			}
			++i;
		}
	}
	for(;j<=tmp;++j)
		pp[j]=su;
	for(i=1;i<=T;++i){
		su=-1;
		for(j=1;j<=tmp && j<=i;++j){
			if(s[i-j]+pp[j]>su)
				su=s[i-j]+pp[j];
		}
		s[i]=su;
	}
	printf("%lld\n",s[T]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}