Pagini recente » Cod sursa (job #323679) | Cod sursa (job #323678)
Cod sursa(job #323678)
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define MAX_N 50005
#define MAX_T 1005
int N, K, T, Tmax;
long long B[MAX_N], R[MAX_N];
set <int> S;
struct peste
{
int t, p;
} A[MAX_N];
struct cmp
{
bool operator()(const peste &a, const peste &b)
{
if(a.t == b.t)
return a.p < b.p;
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;
}
void pre()
{
long long sum(0);
for(int i = 1; i <= N; ++i)
{
if(i <= K)
{
sum += A[i].p;
S.insert(A[i].p);
R[A[i].t] = sum;
continue;
}
set <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;
}
}
}
void solve()
{
long long Sol(0);
for(int i = 0; i <= T; ++i)
{
B[i] = 0;
for(int j = 0; j <= min(i, Tmax); ++j)
B[i] = max(B[i], ((long long)B[i-j] + R[j]));
Sol = max(Sol, B[i]);
}
printf("%lld\n",Sol);
}
int main()
{
freopen("peste.in","rt",stdin);
freopen("peste.out","wt",stdout);
citire();
pre();
solve();
}