Cod sursa(job #197876)

Utilizator alexeiIacob Radu alexei Data 6 iulie 2008 21:30:33
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
//peste fericit
#include<stdio.h>
#include<vector>
#define nmax 50024
#define nmic 1002
using namespace std;

typedef struct{
        long long cost,timp;
        }w;
w v[nmax];

long long sum[nmic],best[nmax];
long long h[nmax];  
long long N,K,Tmax,sf;

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);
}

}

vector< long long > q[nmic];

int main()
{
    freopen("peste.in","r",stdin);
    freopen("peste.out","w",stdout);
    
    scanf("%lld%lld%lld",&N,&K,&Tmax);
    
    long long tmax=0,i,j;
    long long a,b;
    
    for(i=1; i<=N; ++i){
    scanf("%lld%lld\n",&a,&b);
    v[i].cost=a;
    v[i].timp=b;
    if( b>tmax )
    tmax=b;
    q[b].push_back(a);
    }
    
    long long poz=1,sumt=0;
    
    vector< long long >::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("%lld\n",best[Tmax]);

    
    return 0;
}