Pagini recente » Cod sursa (job #317655) | Cod sursa (job #753255) | Cod sursa (job #457627) | Cod sursa (job #3182193) | Cod sursa (job #1130927)
#include <fstream>
#include <algorithm>
#include <queue>
#define MAXN 50005
#define MAXT 1005
#define MAXC 20
using namespace std;
ifstream f("peste.in");
ofstream g("peste.out");
int n,m,t,pesti[MAXN],timp[MAXN],ord[MAXN],mxtimp,cnt,x;
long long pd1[MAXT],pd2[MAXN],mx,sol,S;
char s[MAXC];
bool Comp(int p,int q){
return timp[p]<timp[q];}
struct Comp2{
bool operator()(int p,int q){
return pesti[p]>pesti[q];}};
priority_queue<int,vector<int>,Comp2> pq;
inline int get_int();
int main()
{
int i,j;
f>>n>>m>>t;
f.getline(s,MAXC,'\n');
for(i=1;i<=n;i++){
f.getline(s,MAXC,'\n');
cnt=0;
pesti[i]=get_int();
timp[i]=get_int();
if(timp[i]>mxtimp)
mxtimp=timp[i];
ord[i]=i;}
cnt=0;
sort(ord+1,ord+n+1,Comp);
for(i=1,j=1;i<=mxtimp;i++){
while(j<=n&&timp[ord[j]]<=i){
cnt++;
S+=pesti[ord[j]];
pq.push(ord[j++]);}
while(cnt>m){
x=pq.top();
pq.pop();
S-=pesti[x];
cnt--;}
pd1[i]=S;}
for(i=1;i<=t;i++){
mx=0;
for(j=1;j<=mxtimp&&i>=j;j++)
if(pd1[j]+pd2[i-j]>mx)
mx=pd1[j]+pd2[i-j];
pd2[i]=mx;
if(mx>sol)
sol=mx;}
g<<sol<<'\n';
f.close();
g.close();
return 0;
}
inline int get_int(){
x=s[cnt++]-'0';
while(s[cnt]>='0'&&s[cnt]<='9')
x=x*10+s[cnt++]-'0';
cnt++;
return x;}