Pagini recente » Clasamentul arhivei de probleme | Cod sursa (job #63550) | Cod sursa (job #2770797) | Cod sursa (job #3162587) | Cod sursa (job #2032651)
# include <fstream>
# include <set>
# include <algorithm>
# define DIM 50010
# define f first
# define s second
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
multiset<int> myset;
multiset<int>::iterator it;
pair<int,int> v[DIM];
int n,k,t,i,j;
long long d[DIM],f[1010],sum;
int main () {
fin>>n>>k>>t;
for(i=1;i<=n;i++)
fin>>v[i].s>>v[i].f;
sort(v+1,v+n+1);
for(i=1;i<=k;i++){
f[v[i].f]=v[i].s+f[v[i-1].f];
myset.insert(v[i].s);
}
sum=f[v[k].f];
for(;i<=n;i++){
sum+=v[i].s;
myset.insert(v[i].s);
it=myset.begin();
sum-=(*it);
myset.erase(it);
f[v[i].f]=max(f[v[i].f],sum);
}
for(i=1;i<=t;i++)
for(j=1;j<=min(i,1000);j++)
d[i]=max(d[i],d[i-j]+f[j]);
fout<<d[t]<<"\n";
return 0;
}