Pagini recente » Cod sursa (job #1038549) | Cod sursa (job #2584589) | Cod sursa (job #1746049) | Cod sursa (job #1015004) | Cod sursa (job #172817)
Cod sursa(job #172817)
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
const int N = 50000;
const int T = 50000;
const int TA = 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;
for (;;);
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;
}