Cod sursa(job #164749)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 24 martie 2008 19:23:41
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
const int n_max = 51000;
class set_cmp {
public:
    bool operator() ( const long long  &a, const long long  &b ) { return (a > b); };
};
multiset < int, set_cmp > s;
multiset < int, set_cmp >::iterator it;
pair <int , int >  v[n_max];
pair <int , int >  x[n_max];

long long d[n_max], sol;
int i, j, k, o, n, t, p, q, plase; 

inline long long maxim(long long a, long long b)
{
	if ( a > b)
		return a;
	return b;
}
int main()
{
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	scanf("%d %d %d", &n, &plase, &t);
	for (i = 1; i <= n; ++ i)
	{
		scanf("%d %d", &x[i].second, &x[i].first);
		v[i].first = x[i].first;
	}
	sort(x+1,x+n+1);
	sort(v+1,v+n+1);
	p = 1;
	for (i = 2; i <= n; ++ i)
	{
		if (v[i].first !=v[i-1].first)
			v[++p].first = v[i].first;
	}
	k = 1;
	for (i = 1; i <= p; ++ i)
	{
		while (x[k].first <= v[i].first && k<=n)
			s.insert(x[k++].second);
		it = s.begin();
		
		for (q = 1; q <= plase && q <=s.size(); ++it, ++q)
			v[i].second+=*it;
	}
	d[0] = 1;
	for (j = 0; j <= t; ++ j)
	{
		
		for (i = 1; i <=p; ++ i)
			if (d[j] > 0 && j + v[i].first <= t)
			{
				d[j + tx] = maxim(d[j+v[i].first], d[j]+v[i].second);
				if (d[j+v[i].first] > sol)
					sol = d[j+v[i].first];
			}
	}
	printf("%lld\n", sol-1);
		
	return 0;
}