Pagini recente » Cod sursa (job #1320683) | Cod sursa (job #2423201) | Cod sursa (job #351834) | Cod sursa (job #2344033) | Cod sursa (job #1688691)
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int NM=50005;
int Tmax,i,j, T,n,k, profit[NM];
struct pestisor{int p,t;};
pestisor a[NM];
long long d[NM];
priority_queue< int, vector<int>, greater<int> > Heap;
bool cmp(pestisor a, pestisor b)
{
return (a.t<b.t);
}
void initialize()
{
sort(a+1, a+n+1, cmp);
int i, ind=1, Sum=0;
T=a[n].t;
for(i=1; i<=T; ++i)
{
while(a[ind].t==i)
{
if(Heap.size()<k)
{
Sum += a[ind].p;
Heap.push(a[ind].p);
}
else
if(Heap.size()==k && Heap.top()<=a[ind].p)
{
Sum += a[ind].p-Heap.top();
Heap.pop();
Heap.push(a[ind].p);
}
++ind;
}
profit[i]=Sum;
}
}
int main()
{
freopen("peste.in", "r", stdin);
freopen("peste.out", "w", stdout);
scanf("%d%d%d", &n, &k, &Tmax);
for(i=1; i<=n; ++i) scanf("%d%d", &a[i].p, &a[i].t);
initialize();
for(i=1; i<=Tmax; ++i)
{
d[i]=d[i-1];
for(j=1; i>=j && j<=T; ++j)
d[i]=max( d[i], d[i-j] + profit[j]);
}
printf("%lld\n", d[Tmax]);
return 0;
}