Pagini recente » Cod sursa (job #1639977) | Cod sursa (job #2344536) | Cod sursa (job #1875758) | Cod sursa (job #2639117) | Cod sursa (job #489173)
Cod sursa(job #489173)
#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;
}