Cod sursa(job #163572)

Utilizator tvladTataranu Vlad tvlad Data 22 martie 2008 14:47:26
Problema Peste Scor 30
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 9-a Marime 1.14 kb
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

const int N = 50000;
const int T = 50000;

int n,k,t;
pair<int,int> a[N];
pair<int,int> b[N];
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);
	
	set<int,cmp> s;
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		s.insert(i);
		sum += a[i].second;
		if (s.size() > k) {
			// In cel de-al 2-lea razboi
			// Nae si-a pierdut un coi
			set<int,cmp>::iterator i = s.end();
			--i;
			// Du-te-n chizda ma-tii nae
			// Ministeru n-are coaie
			sum -= a[*i].second;
			s.erase(i);
		}
		b[i].first = sum;
		b[i].second = a[i].first;
	}

	for (int k = 0; k < n; ++k) {
		for (int i = b[k].second; i <= t; ++i) {
			d[i] = max(d[i],d[i-b[k].second]+b[k].first);
		}
	}
	int r = 0;
	for (int i = 0; i <= t; ++i) r = max(r,d[i]);
	printf("%d\n",r);
	return 0;
}