Cod sursa(job #496109)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 27 octombrie 2010 20:06:42
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#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;
	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;
	x=0;
	for (i=1; i<=l; i++)
	{
		for (; p[j].y<=i && j<=n; j++) 
		{
			s.insert(p[j].x);
			x+=p[j].x;
		}
		for (; s.size()>k; ) 
		{
			x-=*s.begin();
			s.erase(s.begin());
		}
		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]);
}