#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
int memo[1024][30];
class FourBlocks { public:
int X, Y;
vector<string> G;
int maxScore(vector <string> grid)
{
X = grid.size();
Y = grid[0].size();
G = grid;
// sentinels
for(int x=0; x<X; ++x)
G[x] += '0';
G.push_back( string(Y+1,'0') );
int baseScore = 0;
for(int x=0; x<X; ++x)
for(int y=0; y<Y; ++y)
baseScore += (G[x][y]=='1');
// memoized search
memset(memo, 0xff, sizeof(memo));
return baseScore + best(0);
}
int best(int y)
{
if( Y <= y )
return 0;
int mask = 0;
for(int x=0; x<X; ++x)
mask |= ((G[x][y]=='.') << x);
if( memo[mask][y] != -1 )
return memo[mask][y];
return memo[mask][y] = best(0, y);
}
int best(int x, int y)
{
if( X <= x )
return best(y+1);
int Max = 0;
if( G[x][y]=='.' )
{
if( G[x+1][y]=='.' && G[x][y+1]=='.' && G[x+1][y+1]=='.' )
{
// can put 4
G[x][y]=G[x+1][y]=G[x][y+1]=G[x+1][y+1] = '4';
Max = max(Max, 16+best(x+2, y));
G[x][y]=G[x+1][y]=G[x][y+1]=G[x+1][y+1] = '.';
}
// can put 1
G[x][y] = '1';
Max = max(Max, 1+best(x+1, y));
G[x][y] = '.';
}
else
{
Max = max(Max, best(x+1, y));
}
return Max;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, FourBlocks().maxScore(grid));}
int main(){
CASE(0)
string grid_[] = {".....1..1..",
"..1.....1.."};
vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
int _ = 70;
END
CASE(1)
string grid_[] = {"...1.",
".....",
".1..1",
".....",
"1...."};
vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
int _ = 73;
END
CASE(2)
string grid_[] = {"...1.",
".1...",
"..1.1",
"1...."};
vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
int _ = 20;
END
CASE(3)
string grid_[] = {".....1...",
".....1...",
"111111111",
".....1...",
".....1..."};
vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
int _ = 117;
END
CASE(4)
string grid_[] = {".........................",
".........................",
".........................",
".........................",
".........................",
".........................",
".........................",
".........................",
".........................",
".........................",
};
vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
int _ = 117;
END
CASE(5)
string grid_[] = {
"1...", "....", "..11",
};
vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
int _ = 36;
END
CASE(6)
string grid_[] = {
"1..", "...", "..1", "..1",
};
vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
int _ = 36;
END
}
// END CUT HERE