Pagini recente » Cod sursa (job #1961261) | Cod sursa (job #2042327) | Cod sursa (job #1235322) | Cod sursa (job #1066715) | Cod sursa (job #1689453)
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int NM=50005;
const int Size=10*NM;
int Tmax,i,j, T,n,k, profit[NM],poz;
struct pestisor{int p,t;};
pestisor a[NM];
long long d[NM];
char Buffer[Size+4];
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;
}
}
bool cifra(char c)
{
return (c>='0' && c<='9');
}
int GetInt()
{
while(!cifra(Buffer[poz])) ++poz;
int nr=0;
while(cifra(Buffer[poz]))
{
nr=nr*10+Buffer[poz]-'0';
++poz;
}
return nr;
}
int main()
{
freopen("peste.in", "r", stdin);
freopen("peste.out", "w", stdout);
fread(Buffer, 1, Size, stdin);
poz=0;
n=GetInt();k=GetInt();Tmax=GetInt();
for(i=1; i<=n; ++i)
{
a[i].p=GetInt();
a[i].t=GetInt();
}
initialize();
for(i=1; i<=Tmax; ++i)
{
d[i]=d[i-1];
for(j=1; j<=i && j<=T; ++j)
d[i]=max( d[i], d[i-j] + profit[j]);
}
printf("%lld\n", d[Tmax]);
return 0;
}