Pagini recente » Cod sursa (job #1791082) | Cod sursa (job #829257) | Cod sursa (job #330366) | Cod sursa (job #1343758) | Cod sursa (job #1130912)
#include <fstream>
#include <algorithm>
#include <queue>
#define MAXN 50005
#define MAXT 1005
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;
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;
int main()
{
int i,j;
f>>n>>m>>t;
for(i=1;i<=n;i++){
f>>pesti[i]>>timp[i];
if(timp[i]>mxtimp)
mxtimp=timp[i];
ord[i]=i;}
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;
}