Cod sursa(job #312224)

Utilizator tvladTataranu Vlad tvlad Data 5 mai 2009 14:31:31
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

const int N_MAX = 50000;
const int T_MAX = 50000;
const int Tp_MAX = 1000;

int n,k,t;
pair<int,int> v[N_MAX];
int c[Tp_MAX+1];
long long d[T_MAX+1];

bool time_cmp ( const pair<int,int> &a, const pair<int,int> &b ) { return a.second == b.second ? a.first > b.first : a.second < b.second; }

int main() {
	freopen("peste.in","rt",stdin);
	freopen("peste.out","wt",stdout);
	scanf("%d %d %d",&n,&k,&t);
	for (int i = 0; i < n; ++i)
		scanf("%d %d",&v[i].first,&v[i].second);
	sort(v,v+n,time_cmp);

	multiset< pair<int,int> > aux;
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		aux.insert(v[i]);
		sum += v[i].first;
		if (aux.size() > k) {
			sum -= aux.begin()->first;
			aux.erase(aux.begin());
		}
		if (sum > c[v[i].second])
			c[v[i].second] = sum;
	}

	long long max = 0;
	for (int i = 1; i <= t; ++i) {
		for (int j = 1; j <= i && j <= Tp_MAX; ++j)
			if (d[i-j] + c[j] > d[i])
				d[i] = d[i-j] + c[j];
		if (d[i] > max) max = d[i];
	}

	printf("%lld\n",max);
	return 0;
}