SRM513-D2-1000

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

class CutTheNumbers{
     public:
     int arr[200000];
     int numbers[16];
     int n,m;
     int cnt;

     int solve(int mask) {
        //cout << "here at mask = " << mask << "\n";
        if(arr[mask] != -1) {
            return arr[mask];
        }
        int &ret = arr[mask];
        ret = 0;
        for(int i = 0; i < cnt; i++) {
            int c_mask = 1 << i;
            if(!(mask&c_mask)) {
                int r = i/m;
                ret = numbers[i] + solve(mask|c_mask);

                //try row
                int row_mask = mask|c_mask;
                int row_sum = numbers[i];
                for(int ci = i+1; ci/m == r; ci++) {
                    int ci_mask = (1 << ci);
                    if(mask&ci_mask) {
                        break;
                    }
                    row_mask |= ci_mask;
                    row_sum = row_sum*10 + numbers[ci];
                    ret = max(ret,row_sum+solve(row_mask));
                }

                int col_mask = mask|c_mask;
                int col_sum = numbers[i];
                for(int ci = i+m; ci < cnt; ci += m) {
                    int ci_mask = (1 << ci);
                    if(mask&ci_mask) {
                        break;
                    }
                    col_mask |= ci_mask;
                    col_sum = col_sum*10 + numbers[ci];
                    ret = max(ret,col_sum+solve(col_mask));
                }
                break;
            }
        }
        return ret;
     }
     int maximumSum(vector <string> board) {
        memset(arr,-1,sizeof(arr));
        n = board.size();
        m = board[0].size();
        //cout << "n is " << n << " m is " << m << "\n";
        cnt = n*m;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                numbers[i*m + j] = board[i][j] - '0';
            }
        }
        return solve(0);
     }
};