Cod sursa(job #496098)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 27 octombrie 2010 19:45:50
Problema Peste Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>
#include <vector>
#include <set>
using namespace std;

int n, k, t, l, a[1010];
long long r[50010];
vector <int> v[1010];
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",&x,&y);
		v[y].push_back(x);
		l=max(l,y);
	}
	for (i=1; i<=l; i++)
		if (v[i].size())
		{
			for (j=0; j<v[i].size(); j++) s.insert(v[i][j]);
			x=0;
			for (it=s.rbegin(), c=1;  c<=k && it!=s.rend(); it++, c++) x+=*it;
			a[i]=x;
		} else a[i]=a[i-1];
	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]);
}