Cod sursa(job #1958702)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 8 aprilie 2017 17:18:12
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.09 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>

const int kMaxDim = 55;

int n, m;
int mat[kMaxDim][kMaxDim], sum[kMaxDim][kMaxDim];
std::map< int64_t, int64_t > dp;

template< int N >
struct Pow {
	static const int64_t pow = 51 * Pow< N-1 >::pow;
};

template<>
struct Pow< 0 > {
		static const int64_t pow = 1;
};

inline int64_t Get(int top, int right, int bottom, int left, int corners) {
	int64_t res = corners * Pow<0>::pow + top * Pow<1>::pow + right * Pow<2>::pow +
			bottom * Pow<3>::pow + left * Pow<4>::pow;
	return res;
}

void SolveRect(int top, int right, int bottom, int left, int corners) {
	int onMargin = top + bottom + left + right;
	for (int i = 0; i < 4; ++i)
		if (corners & (1 << i))
			++onMargin;

	const int v[4] = {top, right, bottom, left};

	int64_t goodSubs = 0;
	for (int config = 0; config < 16; ++config) {
		if ((config | corners) != corners)
			continue;

		int64_t curr = 1;
		int conf = (config | ((config & 1) << 4));

		for (int i = 0; i < 4; ++i) {
			if ((conf & (1 << i)) || (conf & (1 << (i + 1))))
				curr *= (1LL << v[i]);
			else
				curr *= (1LL << v[i]) - 1;
		}

		goodSubs += curr;
	}

	dp[Get(top, right, bottom, left, corners)] = (goodSubs << (50 - onMargin));
}

int main() {
	std::ifstream inputFile("boundingbox.in");
	std::ofstream outputFile("boundingbox.out");

	for (int top = 0; top <= 48; ++top)
		for (int bottom = 0; bottom <= 48; ++bottom)
			for (int right = 0; right <= 48 && (right + 2) * (std::max(top, bottom) + 2) <= 50; ++right)
				for (int left = 0; left <= 48 && (left + 2) * (std::max(top, bottom) + 2) <= 50; ++left)
					for (int corners = 0; corners < 16; ++corners)
						SolveRect(top, right, bottom, left, corners);

	int testCount;
	inputFile >> testCount;

	while (testCount--) {
		inputFile >> n >> m;

		int oneCount = 0;
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j) {
				char ch;
				inputFile >> ch;

				mat[i][j] = ch - '0';
				oneCount += mat[i][j];

				sum[i][j] = sum[i][j - 1] + mat[i][j];
			}

		//one cell
		int64_t res = oneCount * (1LL << (50 - oneCount));

		//one line
		for (int line = 1; line <= n; ++line) {
			for (int col1 = 1; col1 <= m; ++col1) {

				int inCount = mat[line][col1];
				if (mat[line][col1]) {
					for (int col2 = col1 + 1; col2 <= m; ++col2) {
						inCount += mat[line][col2];
						if (mat[line][col2])
							res += (1LL << (50 - oneCount + (inCount - 2))) * (col2 - col1 + 1);
					}
				}

			}
		}

		//one column
		for (int col = 1; col <= m; ++col) {
			for (int line1 = 1; line1 <= n; ++line1) {

				int inCount = mat[line1][col];
				if (mat[line1][col]) {
					for (int line2 = line1 + 1; line2 <= n; ++line2) {
						inCount += mat[line2][col];
						if (mat[line2][col])
							res += (1LL << (50 - oneCount + (inCount - 2))) * (line2 - line1 + 1);
					}
				}

			}
		}

		//rectangle
		for (int col1 = 1; col1 <= m; ++col1) {
			for (int col2 = col1 + 1; col2 <= m; ++col2) {
				for (int line1 = 1; line1 <= n; ++line1) {

					int inCount = sum[line1][col2] - sum[line1][col1 - 1];
					int top = sum[line1][col2 - 1] - sum[line1][col1];
					int left = 0, right = 0;

					for (int line2 = line1 + 1; line2 <= n; ++line2) {
						inCount += sum[line2][col2] - sum[line2][col1 - 1];

						int bottom = sum[line2][col2 - 1] - sum[line2][col1];
						int outCount = oneCount - inCount;

						int corners = (mat[line1][col1] << 0) + (mat[line1][col2] << 1) + (mat[line2][col2] << 2) + (mat[line2][col1] << 3);

						int64_t aux = dp[Get(top, right, bottom, left, corners)] / (1LL << outCount);
						aux = aux * (line2 - line1 + 1) * (col2 - col1 + 1);
						res += aux;

						left += mat[line2][col1];
						right += mat[line2][col2];
					}

				}
			}
		}

		int pow = 50;
		while (res % 2 == 0 && pow && res) {
			pow--;
			res >>= 1;
		}

		if (res == 0)
			pow = 0;
		outputFile << res << '/' << (1LL << pow) << '\n';
	}

	inputFile.close();
	outputFile.close();

	return 0;
}

//Trust me, I'm the Doctor!