Pagini recente » Cod sursa (job #2728361) | Cod sursa (job #656131) | Cod sursa (job #2948510) | Cod sursa (job #2718921) | Cod sursa (job #312224)
Cod sursa(job #312224)
#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;
}