Pagini recente » Cod sursa (job #3181068) | Cod sursa (job #1163626) | Cod sursa (job #607264) | Cod sursa (job #615886) | Cod sursa (job #496107)
Cod sursa(job #496107)
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
struct nr
{
int x, y;
} p[50010];
int cmp(nr a, nr b)
{
return a.y<b.y;
}
int n, k, t, l, a[1010];
long long r[50010];
multiset <int> s;
int main()
{
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d %d %d",&n,&k,&t);
int i, x, y, c, j;
multiset<int> ::reverse_iterator it;
for (i=1; i<=n; i++)
{
scanf("%d %d",&p[i].x, &p[i].y);
l=max(l,p[i].y);
}
sort (p+1, p+n+1, cmp);
j=0;
for (i=1; i<=l; i++)
{
for (; p[j].y<=i && j<=n; j++) s.insert(p[j].x);
x=0;
for (it=s.rbegin(), c=1; c<=k && it!=s.rend(); it++, c++) x+=*it;
a[i]=x;
}
for (i=1; i<=t; i++)
for (j=1; j<=min(i,l); j++)
r[i]=max(r[i], r[i-j]+a[j]);
printf("%lld\n",r[t]);
}