Pagini recente » Cod sursa (job #2306935) | Cod sursa (job #1856866)
#include <fstream>
#include <queue>
#include <algorithm>
#define nmax 50005
using namespace std;
ifstream f("peste.in");
ofstream g("peste.out");
struct plasa{int p;int t;} v[nmax];
priority_queue <int,vector <int>,greater<int> > q;
long long d[nmax];
int n,k,t,s,a[nmax];
int comparing(const plasa &a,const plasa &b)
{
return a.t<b.t;
}
int main()
{
int i,j;
f>>n>>k>>t;
for (i=1;i<=n;i++)
f>>v[i].p>>v[i].t;
sort(v+1,v+n+1,comparing);
for (i=1;i<=n;i++) {
q.push(v[i].p);
s+=v[i].p;
if (q.size()>k) {
s-=q.top();
q.pop();
}
a[v[i].t]=max(a[v[i].t],s);
}
for (i=1;i<=v[n].t;i++)
a[i]=max(a[i],a[i-1]);
for (i=1;i<=t;i++)
for (j=min(i,v[n].t);j>=0;j--)
d[i]=max(d[i],d[i-j]+a[j]);
g<<d[t]<<'\n';
return 0;
}