Cod sursa(job #1707189)

Utilizator david12345Rotari David david12345 Data 24 mai 2016 15:50:56
Problema PalM Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream fi("palm.in");
ofstream fo("palm.out"); 
int n,i,j,k,best,local_max;
int D[505],aib[505][30];
char sir[505];
 
inline int lsb ( int x ){
    return x & -x;
}
 
inline void update_aib2D ( int x , int y , int val ){
    if ( !x || !y ) return ;
     
    for ( int i = x ; i <= n ; i += lsb(i) ){
        for ( int j = y ; j <= 26 ; j += lsb(j) ){
            if ( aib[i][j] < val )
                aib[i][j] = val;
        }
    }
}
 
inline int query_aib2D ( int x , int y ){
    if ( !x || !y ) return 0;
    int s = 0;
     
    for ( int i = x ; i > 0 ; i -= lsb(i) ){
        for ( int j = y ; j > 0 ; j -= lsb(j) ){
            if ( s < aib[i][j] )
                s = aib[i][j];
        }
    }
     
    return s;
}
 
int main () {
     
    fi>>sir+1;
     
    n = strlen(sir+1);
     
    for ( i = n ; i >= 1 ; --i ){
        for ( j = 1 ; j < i ; ++j ){
            if ( sir[j] <= sir[i] ){
                if ( best < D[j] * 2 + 1 )
                    best = D[j] * 2 + 1;
            }
        }
        for ( j = i - 1 ; j ; --j ){
            if ( sir[i] == sir[j] ){
                if ( D[j] < 1 )  {
                    D[j] = 1;
                    update_aib2D(j,sir[j]-'a'+1,1);
                }
                local_max = 0;
                local_max = query_aib2D(j-1,sir[i]-'a'+1);
                if ( D[j] < local_max + 1 )  {
                    D[j] = local_max + 1;
                    update_aib2D(j,sir[j]-'a'+1,local_max+1);
                }
            }
        }
    }
     
    for ( i = 1 ; i <= n ; ++i ){
        if ( D[i] * 2 > best )   best = D[i] * 2;
    }
     
    fo<<best<<endl;
    return 0;
}