Cod sursa(job #172202)

Utilizator raula_sanChis Raoul raula_san Data 5 aprilie 2008 22:14:26
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>

#define maxN 50001
#define maxT 1001

#define pb push_back
#define mp make_pair

#define ff first
#define ss second

using namespace std;

struct Comp
{
	bool operator()(int i, int j)
	{
		return i > j;
	};
};

vector < pair <int, int> > V;
priority_queue <int, vector <int>, Comp> Pq;

int N, K, T;
int D[maxN], Cnt[maxT];

int main()
{
	freopen("peste.in", "rt", stdin);
	freopen("peste.out", "wt", stdout);

	int i, p, t;
	for(scanf("%d %d %d", &N, &K, &T), i=1; i<=N; ++i)
	{
		scanf("%d %d", &p, &t);
		
		V.pb(mp(t, p));
	}

	sort(V.begin(), V.end());

	int s = 0;
	for(i=0; i<N; ++i)
	{
		if(i < K)
		{
			s += V[i].ss;
			Cnt[V[i].ff] = s;
			
			Pq.push(V[i].ss);
		}
		else
		{
			int c = Pq.top();
			
			if(V[i].ss > c)
			{
				Pq.pop();
				s -= c;
				s += V[i].ss;
				Pq.push(V[i].ss);
				
				Cnt[V[i].ff] = s;
			}
		}
	}
	
	for(i=1; i<=1000; ++i)
		if(Cnt[i-1] > Cnt[i]) Cnt[i] = Cnt[i-1];

    int j;
	for(i=1; i<=T; ++i)
		for(j=1; j<=1000 && j<=i; ++j)
			if(D[i] < D[i-j] + Cnt[j])
				D[i] = D[i-j] + Cnt[j];
				
	printf("%d", D[T]);
	
	fclose(stdin);
	fclose(stdout);

	return 0;
}