Pagini recente » Cod sursa (job #235836) | Cod sursa (job #138153) | Cod sursa (job #703726) | Cod sursa (job #692350) | Cod sursa (job #1413399)
#include <fstream>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
#define NMAX 50007
#define p second
#define t first
ifstream f("peste.in");
ofstream g("peste.out");
int Tt,N,K,i,j,tmax;
long long sum;
pair < int , int > x[NMAX];
long long d[NMAX],bst[NMAX];
priority_queue < int > pq;
void readprec()
{
f >> N >> K >> Tt;
Tt += 1;
for (i=1;i<=N;++i)
{
f >> x[i].p >> x[i].t;
tmax = max (tmax , x[i].t);
}
sort(x+1,x+N+1);
}
void buildd()
{
j = 1;
for (i=1;i<=tmax;++i)
{
// in i unitati de timp, vad cati pesti prind
while (j<=N && x[j].t <= i)
{
pq.push(-x[j].p);
sum += 1ll * x[j].p;
++j;
}
while (pq.size() > K)
{
sum += 1ll * pq.top();
pq.pop();
}
d[i+1] = sum;
}
tmax += 1;
/*
for (i=1;i<=tmax;++i)
g << d[i] << '\n';
g << "////////////////////////" << '\n';
*/
}
void solve()
{
for (i=1;i<=Tt;++i)
for (j=1;j<=min(i,tmax);++j)
bst[i] = max(bst[i] , bst[i-j+1] + d[j]);
g << bst[Tt] << '\n';
}
int main()
{
readprec();
buildd();
solve();
return 0;
}