Cod sursa(job #172797)

Utilizator tvladTataranu Vlad tvlad Data 6 aprilie 2008 19:29:29
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

const int N = 3;//50000;
const int T = 5;//50000;
const int TA = 5;//1000;

int n,k,t, tmax;
pair<int,int> a[N];
int ax[TA+1];
int d[T+1];

class cmp {
public:
	bool operator() ( const int &x, const int &y ) {
		return (a[x].second > a[y].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",&a[i].second,&a[i].first);
	}
	sort(a,a+n);
	tmax = a[n-1].first;
	
	set<int,cmp> s;
	for (int i = 0; i < n; ++i) {
		s.insert(i);
		ax[a[i].first] += a[i].second;
		if (s.size() > k) {
			set<int,cmp>::iterator it = s.end(); --it;
			ax[a[i].first] -= a[*it].second;
			s.erase(it);
		}
	}
	for (int i = 1; i <= tmax; ++i) ax[i] += ax[i-1];

	d[0] = 0;
	for (int i = 1; i <= t; ++i) {
		d[i] = 0;
		for (int j = 1; j <= i && j <= tmax; ++j) {
			if (d[i-j]+ax[j] > d[i]) {
				d[i] = d[i-j]+ax[j];
			}
		}
	}
	printf("%d\n",d[t]);
	return 0;
}