Cod sursa(job #197881)

Utilizator alexeiIacob Radu alexei Data 6 iulie 2008 21:42:46
Problema Peste Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
//scraping...
#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;
    }

    long long temp;

    for(i=1; i<=Tmax; ++i){     
             for(j=1; j<=tmax; ++j)    
                       if(i-j>=0){
                       temp=best[i-j]+sum[j];     
                           if( temp>best[i] )
                           best[i]=temp;
                       }
             }
     
     printf("%lld\n",best[Tmax]);

    
    return 0;
}