Artifact Content
Not logged in

Artifact 3aabd385e4b10b4a14a416f01a477aa280d34f7d


#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;

class UnfoldingTriangles { public:
	int solve(vector <string> grid, int unfoldLimit) 
	{
		int X = grid[0].size();
		int Y = grid.size();

		int Max = -1;
		// top-right
		for(int y=0; y<Y; ++y)
			for(int x=X; x>=1; --x)
			{
				int numTri = 0;
				// size
				for(int n=1; x-n>=0 && y+n<=Y; ++n)
				{
					// right-check
					if( x<X && grid[y+n-1][x]=='#' )
						goto NextTopRight;
					// diag-check
					if( grid[y+n-1][x-n]!='/' )
						goto NextTopRight;
					// inner-check
					for(int k=1; k<n; ++k) {
						if( grid[y+n-1][x-k] == '.' )
							goto NextTopRight;
						if( grid[y+n-1][x-k] == '/' )
							if( ++numTri > unfoldLimit )
								goto NextTopRight;
					}
					// bottom-check
					bool ok = true;
					if( y+n == Y )
						ok = true;
					else
						for(int k=1; k<=n; ++k) {
							if( grid[y+n][x-k] == '#' )
								{ok=false; break;}
						}

					// update
					if( ok )
						Max = max( Max, n*(n+1)/2 );
				}
			NextTopRight:;
			}

		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(_, UnfoldingTriangles().solve(grid, unfoldLimit));}
int main(){

CASE(0)
	string grid_[] = {".../",
 "../#",
 "./#/",
 "/#//"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int unfoldLimit = 4; 
	int _ = 10; 
END
CASE(1)
	string grid_[] = {".../",
 "../#",
 "./#/",
 "/#//"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int unfoldLimit = 2; 
	int _ = 3; 
END
CASE(2)
	string grid_[] = {"////",
 "////",
 "////",
 "////"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int unfoldLimit = 5; 
	int _ = 6; 
END
CASE(3)
	string grid_[] = {".....#...",
 "....###.."};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int unfoldLimit = 10; 
	int _ = -1; 
END
CASE(4)
	string grid_[] = {"#//#",
 "#//#",
 "####",
 "///#"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int unfoldLimit = 4; 
	int _ = 1; 
END
CASE(5)
	string grid_[] = {".../.../",
 "../#..//",
 "./.#.///",
 "/###...."};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int unfoldLimit = 3; 
	int _ = 6; 
END
CASE(6)
	string grid_[] = {
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 "//////////////////////////////////////////////////",
 };
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int unfoldLimit = 2500; 
	int _ = 6; 
END

}
// END CUT HERE