Pagini recente » Cod sursa (job #1969415) | Cod sursa (job #2312854) | Cod sursa (job #1953777) | Cod sursa (job #2742245) | Cod sursa (job #2636336)
#include<fstream>
#include<algorithm>
#include<queue>
#define p second
#define t first
using namespace std;
ifstream fi("peste.in");
ofstream fo("peste.out");
int n,k,T,i,j,sumq,Nrpesti[1005];
pair<int,int> A[50005];
priority_queue<int> Q;
long long Dp[50005];
int main()
{
fi>>n>>k>>T;
for(i=1; i<=n; i++)
fi>>A[i].p>>A[i].t;
sort(A+1,A+n+1);
for(i=1; i<=n; i++)
{
sumq+=A[i].p;
Q.push(-A[i].p);
if(Q.size()>k)
{
sumq+=Q.top();
Q.pop();
}
Nrpesti[A[i].t]=sumq;
}
for(i=1; i<=1000; i++)
Nrpesti[i]=max(Nrpesti[i],Nrpesti[i-1]);
for(i=1; i<=T; i++)
{
Dp[i]=Dp[i-1];
for(j=1; j<=min(i,1000); j++)
Dp[i]=max(Dp[i],Dp[i-j]+Nrpesti[j]);
}
fo<<Dp[T]<<"\n";
fi.close();
fo.close();
return 0;
}