Pagini recente » Cod sursa (job #796852) | Cod sursa (job #2968210) | Cod sursa (job #128930) | Cod sursa (job #315218) | Cod sursa (job #163571)
Cod sursa(job #163571)
#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;
}