Pagini recente » Cod sursa (job #936529) | Rezultatele filtrării | Rezultatele filtrării | Pusculita | Cod sursa (job #204636)
Cod sursa(job #204636)
using namespace std;
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <utility>
#define IN "peste.in"
#define OUT "peste.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<16
#define t first
#define p second
int TM,N,K,Ttotal;
vector< pair<int,int> > V(N_MAX);
int A[N_MAX],S[N_MAX];
multiset<int> M;
void scan()
{
freopen(IN, "r",stdin);
freopen(OUT, "w",stdout);
scanf("%d %d %d\n",&N,&K,&Ttotal);
V.resize(N);
FOR(i,1,N)
{
scanf("%d%d", &V[i].p,&V[i].t);
TM = max(V[i].t,TM);
}
sort(V.begin(), V.end() );
}
void solve()
{
int ki,k(1);
bool ok(0);
FOR(i,1,Ttotal)
{
ok = false;
while(V[k].t <= i && k<=N)
M.insert(V[k].p),
++k,ok=true;
if(!ok)
{
A[i] = A[i-1];
continue;
}
multiset<int>::iterator it;
ki = M.size() - K;
if(ki > 0)
{
for(it = M.begin(); it != M.end() && ki>0;++it)
M.erase(it),--ki;
}
for(it = M.begin(); it != M.end();++it)
A[i] += *it;
}
FOR(i,0,Ttotal)
for(int j=i-1;j>= max(0,i-TM);--j)
S[i] = max(S[i], S[j] + A[i-j]);
printf("%d\n", S[Ttotal]);
}
int main()
{
scan();
solve();
return 0;
}