Pagini recente » Monitorul de evaluare | Cod sursa (job #456489) | Cod sursa (job #806446) | Cod sursa (job #474464) | Cod sursa (job #532043)
Cod sursa(job #532043)
#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;
}