Pagini recente » Cod sursa (job #2788537) | Cod sursa (job #924152) | Cod sursa (job #641963) | Cod sursa (job #2891967) | Cod sursa (job #851110)
Cod sursa(job #851110)
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define MAX_N 100005
int N, K, T, Tmax;
long long B[MAX_N], R[MAX_N];
multiset <int> S;
struct peste
{
int t, p;
} A[MAX_N];
struct cmp
{
bool operator()(const peste &a, const peste &b)
{
return a.t < b.t;
}
};
void citire()
{
scanf("%d %d %d",&N, &K, &T);
for(int i = 1; i <= N; ++i)
scanf("%d %d",&A[i].p, &A[i].t);
sort(A+1, A+N+1, cmp());
Tmax = A[N].t + 1;
}
void pre()
{
long long sum(0);
for(int i = 1; i <= N; ++i)
{
if(S.size() < K)
{
S.insert(A[i].p);
sum += A[i].p;
}
else
{
multiset <int> ::iterator it = S.begin();
if(*it < A[i].p)
{
sum -= *it;
S.erase(it);
S.insert(A[i].p);
sum += A[i].p;
}
}
R[A[i].t] = sum;
}
for(int i = 0; i <= Tmax; ++i)
R[i] = max(R[i], R[i-1]);
}
void solve()
{
for(int i = 1; i <= T; ++i)
for(int j = 1; j <= Tmax; ++j)
{
if(i < j) continue;
B[i] = max(B[i], B[i-j] + R[j]);
}
printf("%lld\n",B[T]);
}
int main()
{
freopen("peste.in","rt",stdin);
freopen("peste.out","wt",stdout);
citire();
pre();
solve();
}