Pagini recente » Cod sursa (job #2796533) | Cod sursa (job #1401288) | Cod sursa (job #137196) | Cod sursa (job #1801033) | Cod sursa (job #2034090)
#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
struct grup{
int t;
int p;
};
int cnp(grup a, grup b)
{
if(a.t==b.t)
return a.p<b.p;
else
return a.t<b.t;
}
long long i, n,ok, j, aux[50002],k,nr, t;
grup v[50002];
priority_queue <int, vector<int>, greater<int> > w;
int main(){
fin>>n>>k>>t;
for(i=1;i<=n;i++)
{
fin>>v[i].p>>v[i].t;
}
sort(v+1, v+n+1, cnp);
for(i=1;i<=k;i++)
{
aux[v[i].t]=v[i].p+aux[v[i-1].t];
w.push(v[i].p);
}
ok=aux[v[k].t];
for(i=k+1;i<=n;i++)
{
ok+=v[i].p;
w.push(v[i].p);
ok-=w.top();
w.pop();
aux[v[i].t]=max(aux[v[i].t], ok);
}
for(i=1;i<=t;i++)
for(j=1;j<=i&&j<=1000;j++)
aux[i]=max(aux[i], aux[i-j]+aux[j]);
fout<<aux[t];
fin.close();
fout.close();
return 0;
}