Cod sursa(job #532043)

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