Pagini recente » Cod sursa (job #1168924) | Cod sursa (job #1142930) | Cod sursa (job #1284785) | Cod sursa (job #2302181) | Cod sursa (job #532049)
Cod sursa(job #532049)
#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;
}