Pagini recente » Monitorul de evaluare | Cod sursa (job #2624417) | Cod sursa (job #491661) | Cod sursa (job #1573186) | Cod sursa (job #2097328)
#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
priority_queue< int , vector<int> , greater<int> > qu;
int n,m,k,timp,j,i;
long long sum,best[50010],aux[50010];
struct date_plase
{
int pes,tim;
} v[50010];
bool cmpp(date_plase x, date_plase y)
{
if(x.tim == y.tim)
return x.pes < y.pes;
else
return x.tim < y.tim;
}
int main()
{
fin>>n>>k>>timp;
for(i=1;i<=n;++i)
{
fin>>v[i].pes>>v[i].tim;
}
sort(v+1,v+n+1,cmpp);
for(i=1;i<=n;++i)
{
qu.push(v[i].pes);
sum+=v[i].pes;
if(qu.size() > k)
{
sum-=qu.top();
qu.pop();
}
aux[v[i].tim]=max(aux[v[i].tim], sum );
}
for(i=1;i<=timp;++i)
{
for(j=0; j<=min( i, v[n].tim);++j)
best[i]=max(best[i],best[i-j]+aux[j]);
}
fout<<best[timp];
return 0;
}