Cod sursa(job #197870)

Utilizator alexeiIacob Radu alexei Data 6 iulie 2008 20:45:07
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
//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("peste.in","r",stdin);
    freopen("peste.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;
}