Pagini recente » Cod sursa (job #1058771) | Cod sursa (job #2458914) | Cod sursa (job #2990742) | Cod sursa (job #404719) | Cod sursa (job #197869)
Cod sursa(job #197869)
//peste fericit
#include<stdio.h>
#include<algorithm>
#define nmax 50024
#define nmic 1024
using namespace std;
typedef struct{
long long cost,timp;
}q;
q v[nmax];
long long sum[nmic],best[nmax];
long long h[nmax];
long long N,K,Tmax,sf;
inline long long cmp(q A,q B)
{
return A.timp<B.timp;
}
void change(const long long a,const long long b)
{
h[a]^=h[b];
h[b]^=h[a];
h[a]^=h[b];
}
void down(long long stuff)
{
long long right,left,ctrl;
left=stuff<<1;
right=left+1;
ctrl=stuff;
if( left<=sf ){
if( h[left]<h[ctrl] )
ctrl=left;
if( right<=sf )
if( h[right]<h[ctrl])
ctrl=right;
}
if( stuff!=ctrl )
{
change(stuff,ctrl);
down(ctrl);
}
}
void upp(long long stuff)
{
long long father=stuff>>1;
long long ctrl=stuff;
if( father>=1 )
if( h[father]>h[ctrl] )
ctrl=father;
if( ctrl!=stuff )
{
change(ctrl,stuff);
if( ctrl!=1 )
upp(ctrl);
}
}
int main()
{
freopen("pesti.in","r",stdin);
freopen("pesti.out","w",stdout);
scanf("%lld%lld%lld",&N,&K,&Tmax);
long long solfin=0;//reminiscenta comunista
long long tmax=0,i,j;
for(i=1; i<=N; ++i){
scanf("%lld%lld\n",&v[i].cost,&v[i].timp);
if( v[i].timp>tmax )
tmax=v[i].timp;
}
sort(v+1,v+N+1,cmp);
long long poz=1,sumt=0;
for(i=1; i<=tmax; ++i)
{
while( v[poz].timp == i )
{
++sf;
h[sf]=v[poz].cost;
sumt+=v[poz].cost;
if( sf>1 )
upp(sf);
if( sf>K ){
sumt-=h[1];
change(sf,1);
down(1);
--sf;
}
++poz;
}
sum[i]=sumt;
}
for(i=1; i<=Tmax; ++i){
for(j=1; j<=tmax; ++j)
if(i-j>=0)
best[i]=max(best[i],best[i-j]+sum[j]);
else
break;
}
printf("%lld\n",best[Tmax]);
return 0;
}