Problem: Example

Input

4
B
W
WB
WB


Output

5

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;
 
 
#define SIZE 40
 
struct Info{
 
    Info(int arg_num,ll arg_sum_value){
        num = arg_num;
        sum_value = arg_sum_value;
    }
    bool operator<(const struct Info &arg) const{
 
        return sum_value < arg.sum_value;
    }
 
    int num;
    ll sum_value;
};
 
int N,first_N;
ll POW[SIZE],POW2[SIZE];
ll value[SIZE];
int table[8000005];
char buf[SIZE+1];
int num_box[SIZE];
 
 
//簡易化のため、要素数を2のべき乗にする関数
void init(int first_N){
    while(N < first_N)N *= 2;
}
 
void update(int loc,ll value){
    loc += N-1;
 
    table[loc] = value;
 
    if(N == 1)return;
 
    int parent = (loc-1)/2;
 
    while(true){
        table[parent] = max(table[2*parent+1],table[2*parent+2]);
 
        if(parent == 0)break;
        else{
            parent = (parent-1)/2;
        }
    }
}
 
 
//任意の区間の最大を求める関数
int query(int search_left,int search_right,int node_id,int node_left,int node_right){ //table[node_id]に、node_left～node_righの区間の最小値が記録されているということt
 
    //今回のノードが検索区間をカバーしていなければ、結果に関係ない値を返す
    if(search_right < node_left || search_left > node_right)return -BIG_NUM;
 
    //今回のノードの区間が、検索区間の部分区間である場合、今回のノードの値を返す
    if(search_left <= node_left && search_right >= node_right){
        return table[node_id];
    }
 
    //今回のノードの区間に、一部検索区間と重なっている区間がある場合→再帰的に子どもに尋ねる
    int left_max = query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2);
    int right_max = query(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right);
 
    return max(left_max,right_max);
}
 
 
 
 
int main(){
 
    POW[39] = 1;
    for(int i = 38; i >= 0; i--){
 
        POW[i] = POW[i+1]*2;
    }
 
    int first_N;
    scanf("%d",&first_N);
 
    int length;
 
    for(int i = 0; i < first_N; i++){
 
        scanf("%s",buf);
 
        for(length = 0; buf[length] != '\0'; length++);
        num_box[i] = length; //箱の数
 
        //pileを数値化する(bottom→top方向)
        ll tmp = 0;
        ll count = 0;
 
        if(buf[0] == 'B'){
 
            while(count < length && buf[count] == 'B')count++;
            tmp = POW[0]*count;
 
        }else{
 
            while(count < length && buf[count] == 'W')count++;
            tmp = POW[0]*(-1)*count;
        }
 
        int rank = 1;
 
        for(int k = count; k < length; k++){
 
            if(buf[k] == 'B'){
 
                tmp += POW[rank];
 
            }else{
 
                tmp -= POW[rank];
            }
            rank++;
        }
        value[i] = tmp;
    }
 
    //半分全列挙
    POW2[0] = 1;
    for(int i = 1; i < SIZE; i++){
 
        POW2[i] = POW2[i-1]*2;
    }
 
    int first_max = (first_N-1)/2;
    int first_num = first_max+1,second_num = first_N-first_num;
 
    vector<Info> FIRST,SECOND;
 
    //前半
    for(int state = 0; state < POW2[first_num]; state++){
 
        int num = 0;
        ll sum_value = 0;
 
        for(int loop = 0; loop < first_num; loop++){
            if(state & (1 << loop)){
                num += num_box[loop];
                sum_value += value[loop];
            }
        }
 
        FIRST.push_back(Info(num,sum_value));
    }
    sort(FIRST.begin(),FIRST.end()); //昇順
 
    //後半
    for(int state = 0; state < POW2[second_num]; state++){
 
        int num = 0;
        ll sum_value = 0;
 
        for(int loop = 0; loop < second_num; loop++){
            if(state & (1 << loop)){
                num += num_box[first_num+loop];
                sum_value += value[first_num+loop];
            }
        }
 
        SECOND.push_back(Info(num,sum_value));
    }
    sort(SECOND.begin(),SECOND.end());
 
    N = 1;
    init(SECOND.size());
 
    for(int i = 0; i <= 2*N-2; i++)table[i] = -BIG_NUM;
    for(int i = 0; i < SECOND.size(); i++){
 
        update(i,SECOND[i].num);
    }
 
    int ans = 0;
    int L,R,mid;
    int left,right;
 
    for(int i = 0; i < FIRST.size(); i++){
 
        //FIRST[i].sum_value+SECOND[k].sum_value == 0となるkの範囲を求める
 
        L = 0,R = SECOND.size()-1,mid = (L+R)/2;
        left = BIG_NUM; //左端
 
        while(L <= R){
 
            if(FIRST[i].sum_value+SECOND[mid].sum_value == 0){
 
                left = mid;
                R = mid-1;
 
            }else if(FIRST[i].sum_value+SECOND[mid].sum_value < 0){
 
                L = mid+1;
 
            }else{ //FIRST[i].sum_value+SECOND[mid].sum_value > 0
 
                R = mid-1;
 
            }
            mid = (L+R)/2;
        }
        if(left == BIG_NUM)continue;
 
        L = 0,R = SECOND.size()-1,mid = (L+R)/2;
        right = -BIG_NUM; //右端
 
        while(L <= R){
 
            if(FIRST[i].sum_value+SECOND[mid].sum_value == 0){
 
                right = mid;
                L = mid+1;
 
            }else if(FIRST[i].sum_value+SECOND[mid].sum_value < 0){
 
                L = mid+1;
 
            }else{ //FIRST[i].sum_value+SECOND[mid].sum_value > 0
 
                R = mid-1;
            }
            mid = (L+R)/2;
        }
        if(right == -BIG_NUM)continue;
 
        ans = max(ans,FIRST[i].num+query(left,right,0,0,N-1));
    }
 
    printf("%d\n",ans);
 
    return 0;
}