Cod sursa(job #323679)

Utilizator Mishu91Andrei Misarca Mishu91 Data 13 iunie 2009 00:55:23
Problema Peste Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

#define MAX_N 50005

int N, K, T, Tmax;
long long B[MAX_N], R[MAX_N];
set <int> S;

struct peste
{
	int t, p;
} A[MAX_N];

struct cmp
{
	bool operator()(const peste &a, const peste &b)
	{
		if(a.t == b.t)
			return a.p < b.p;
		return a.t < b.t;
	}
};

void citire()
{
	scanf("%d %d %d",&N, &K, &T);
	
	for(int i = 1; i <= N; ++i)
		scanf("%d %d",&A[i].p, &A[i].t);
	
	sort(A+1, A+N+1, cmp());
	Tmax = A[N].t;
}

void pre()
{
	long long sum(0);
	for(int i = 1; i <= N; ++i)
	{
		if(i <= K)
		{
			sum += A[i].p;
			S.insert(A[i].p);
			R[A[i].t] = sum;
			continue;
		}
		
		set <int> ::iterator it = S.begin();
		if(*it < A[i].p)
		{
			sum -= *it;
			S.erase(it);
			S.insert(A[i].p);
			sum += A[i].p;
			R[A[i].t] = sum;
		}
	}
}

void solve()
{
	long long Sol(0);
	for(int i = 0; i <= T; ++i)
	{
		B[i] = 0;
		for(int j = 0; j <= min(i, Tmax); ++j)
			B[i] = max(B[i], B[i-j] + R[j]);
		Sol = max(Sol, B[i]);
	}
	printf("%lld\n",Sol);
}

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