Pagini recente » Cod sursa (job #1802038) | Cod sursa (job #159000) | Cod sursa (job #3140380) | Cod sursa (job #2755002) | Cod sursa (job #197878)
Cod sursa(job #197878)
//peste fericit
#include<stdio.h>
#include<vector>
#define nmax 50024
#define nmic 1002
using namespace std;
typedef struct{
int cost,timp;
}w;
w v[nmax];
long long sum[nmic],best[nmax];
int h[nmax];
int N,K,Tmax,sf;
void change(const int a,const int b)
{
h[a]^=h[b];
h[b]^=h[a];
h[a]^=h[b];
}
void down(int stuff)
{
int 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(int stuff)
{
int father=stuff>>1;
int ctrl=stuff;
if( father>=1 )
if( h[father]>h[ctrl] )
ctrl=father;
if( ctrl!=stuff )
{
change(ctrl,stuff);
if( ctrl!=1 )
upp(ctrl);
}
}
vector< int > q[nmic];
int main()
{
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d%d%d",&N,&K,&Tmax);
int tmax=0,i,j;
int a,b;
for(i=1; i<=N; ++i){
scanf("%d%d\n",&a,&b);
v[i].cost=a;
v[i].timp=b;
if( b>tmax )
tmax=b;
q[b].push_back(a);
}
int poz=1;
long long sumt=0;
vector< int >::iterator it;
for(i=1; i<=tmax; ++i)
{ it=q[i].begin();
while( it!=q[i].end() )
{
++sf;
h[sf]=*it;
sumt+=*it;
if( sf>1 )
upp(sf);
if( sf>K ){
sumt-=h[1];
change(sf,1);
down(1);
--sf;
}
++it;
}
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("%d\n",best[Tmax]);
return 0;
}