Pagini recente » Cod sursa (job #1804786) | Cod sursa (job #1578986) | Cod sursa (job #1111669) | Cod sursa (job #606505) | Cod sursa (job #1450301)
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cctype>
using namespace std;
const int Bsize = (1 << 16);
struct aww
{
int fish,t;
};
int n,k,T,i,Max,s,j,p;
long long aux[1010];
long long D[50010];
aww v[50010];
char Buffer[Bsize];
priority_queue < int, vector <int>, greater <int> >H;
inline bool cmp(aww A,aww B)
{
if(A.t<B.t)
return true;
if(A.t==B.t && A.fish<B.fish)
return true;
return false;
}
void get_number(int &x)
{
x = 0;
while (!isdigit(Buffer[p]))
{
if (p == Bsize - 1)
{
fread(Buffer , 1 , Bsize , stdin);
p = 0;
}
else ++p;
}
while (isdigit(Buffer[p]))
{
x = x * 10 + Buffer[p] - '0';
if (p == Bsize - 1)
{
fread(Buffer , 1 , Bsize , stdin);
p = 0;
}
else ++p;
}
}
int main()
{
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
fread(Buffer , 1 , Bsize , stdin); p = 0;
get_number(n); get_number(k); get_number(T);
for(i=1; i<=n; ++i)
{
get_number(v[i].fish); get_number(v[i].t);
if(v[i].t>Max)
Max=v[i].t;
}
sort(v+1,v+n+1,cmp);
for(i=1; i<=n; ++i)
{
H.push(v[i].fish);
s+=v[i].fish;
if(i>k)
{
s-=H.top();
H.pop();
}
aux[v[i].t]=s;
}
for(i=1; i<=Max; ++i)
aux[i]=max(aux[i-1],aux[i]);
for(i=1; i<=T; ++i)
for(j=1; j<=i && j<=Max; ++j )
D[i]=max(D[i],D[i-j]+aux[j]);
printf("%lld\n",D[T]);
return 0;
}