Pagini recente » Cod sursa (job #2817371) | Cod sursa (job #765414) | Cod sursa (job #2543427) | Cod sursa (job #1508649) | Cod sursa (job #2097317)
#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,sum,best[50010],aux[50010],j,i,sol;
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);
sol+=v[i].pes;
if(qu.size() > k)
{
sol-=qu.top();
qu.pop();
}
aux[v[i].tim]=max(aux[v[i].tim], sol );
}
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;
}