Pagini recente » Cod sursa (job #1605320) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #95925) | Cod sursa (job #204623)
Cod sursa(job #204623)
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];
struct comp
{
bool operator () (int x,int y) const
{ return V[x].p < V[y].p; }
};
multiset<int, comp > M;
void scan()
{
freopen(IN, "r",stdin);
freopen(OUT, "w",stdout);
scanf("%d %d %d\n",&N,&K,&Ttotal);
FOR(i,1,N)
{
scanf("%d%d", &V[i].p,&V[i].t);
TM = max(V[i].t,TM);
}
V.resize(N);
sort(V.begin()+1, V.end()+1 );
}
void solve()
{
int ki,k(1);
FOR(i,1,Ttotal)
{
while(V[k].t <= i && k<=N)
M.insert(k),
++k;
multiset<int, comp >::iterator it;
ki = M.size() - K;
for(it = M.begin(); it != M.end() && ki>0;++it)
M.erase(it),--ki;
for(it = M.begin(); it != M.end();++it)
A[i] += V[*it].p;
}
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;
}