Cod sursa(job #22505)

Utilizator cos_minBondane Cosmin cos_min Data 26 februarie 2007 19:13:35
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <stdio.h>
#include <vector>
#include <iterator>
using namespace std;

#define in "lupu.in"
#define out "lupu.out"

vector< vector<unsigned int> > a;
vector<unsigned int> timp;
vector<unsigned int> val;
vector<bool> sel;
unsigned int n, d, t;

int main()
{
    int tmax=0, x;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%u%u%u",&n,&t,&d);
    
    val.resize(n+1);
    a.resize(2);
    timp.resize(n+1);
    sel.resize(n+1);
    
    int i, j;
    
    for ( i = 1; i <= n; i++ )
    {
        scanf("%u%u",&x,&val[i]);
        
        if ( x > t ) timp[i] = -1;
        else         timp[i] = (t-x)/d;  
        
        if ( tmax < (t-x)/d ) tmax = (t-x)/d;
    }
    
    for ( i = 0; i <= 1; i++ ) a[i].resize(tmax+1);
    
    int poz, maxim;
    
    for ( i = 1; i <= n; i++ )
        if ( a[0][tmax] < val[i] && timp[i] >= tmax ) a[0][tmax] = val[i], poz = i;
    
    sel[poz] = 1;
    
    for ( j = tmax-1; j >= 0; j-- ) 
    {
        maxim = 0;
        for ( i = 1; i <= n; i++ )
        {
            if ( sel[i] || timp[i] < j || timp[i] == -1 ) continue;
            
            if ( a[1][j] < a[0][j+1] + val[i] )
            {
                 a[1][j] = a[0][j+1] + val[i];
                 if ( maxim < a[1][j] ) maxim = a[1][j], poz = i;
            }
        }
        a[0][j] = maxim;
        sel[poz] = 1;
    }
    
    /* for ( int j = 0; j <= tmax; j++ ) 
     {
         for ( int i = 0; i <= 1; i++ )
         {
             printf("%d ", a[i][j] );
         }
         printf("\n");
         
     }*/
    
    //for ( int i = 1; i <= n; i++ ) printf("%d ", );
    
    printf("%u",a[0][0]);
}

/*
#include <stdio.h>
#include <vector>
#include <iterator>
using namespace std;

#define in "lupu.in"
#define out "lupu.out"

vector< vector<int> > a;
vector<int> timp;
vector<int> val;
vector<bool> sel;
int n, d, t;

int main()
{
    int tmax=0, x;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d%d",&n,&t,&d);
    
    val.resize(n+1);
    a.resize(2);
    timp.resize(n+1);
    sel.resize(n+1);
    
    for ( int i = 1; i <= n; i++ )
    {
        scanf("%d%d",&x,&val[i]);
        
        if ( x > t ) timp[i] = -1;
        else         timp[i] = (t-x)/d;  
        
        if ( tmax < (t-x)/d ) tmax = (t-x)/d;
    }
    
    for ( int i = 0; i <= 1; i++ ) a[i].resize(tmax+1);
    
    int poz, maxim;
    
    for ( int i = 1; i <= n; i++ )
        if ( a[0][tmax] < val[i] && timp[i] >= tmax ) a[0][tmax] = val[i], poz = i;
    
    sel[poz] = 1;
    
    for ( int j = tmax-1; j >= 0; j-- ) 
    {
        maxim = 0;
        for ( int i = 1; i <= n; i++ )
        {
            if ( sel[i] || timp[i] < j || timp[i] == -1 ) continue;
            
            if ( a[1][j] < a[0][j+1] + val[i] )
            {
                 a[1][j] = a[0][j+1] + val[i];
                 if ( maxim < a[1][j] ) maxim = a[1][j], poz = i;
            }
        }
        a[0][j] = maxim;
        sel[poz] = 1;
    }
    
    /* for ( int j = 0; j <= tmax; j++ ) 
     {
         for ( int i = 0; i <= 1; i++ )
         {
             printf("%d ", a[i][j] );
         }
         printf("\n");
         
     }
    
    //for ( int i = 1; i <= n; i++ ) printf("%d ", );
    
    printf("%d",a[0][0]);
}

*/