Cod sursa(job #1759167)

Utilizator Ionut.popescuLiviu Rebreanu Ionut.popescu Data 18 septembrie 2016 16:29:13
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <vector>
#include <string>
#include <functional>

using namespace std;

int main() {
	ifstream cin("boundingbox.in");
	ofstream cout("boundingbox.out");
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	
	int num_tests; cin >> num_tests;
	for (int iter = 0; iter < num_tests; iter += 1) {
		int n, m; cin >> n >> m;
		vector<vector<int>> partial_sum(n + 1, vector<int>(m + 1, 0));
		int num_1 = 0;
		for (int i = 1; i <= n; i += 1) {
			string line; cin >> line;
			for (int j = 1; j <= m; j += 1) {
				partial_sum[i][j] = partial_sum[i - 1][j] + partial_sum[i][j - 1] - partial_sum[i - 1][j - 1] + line[j - 1] - '0';
				num_1 += line[j - 1] - '0';
			}
		}
		auto get_sum = [&](const int& x1, const int &y1, const int &x2, const int &y2) {
			if (x2 < x1 || y2 < y1) {
				return 0;
			}
			return partial_sum[x2][y2] - partial_sum[x1 - 1][y2] - partial_sum[x2][y1 - 1] + partial_sum[x1 - 1][y1 - 1];
		};
		long long answer = 0LL;
		for (int i = 1; i <= n; i += 1) for (int j = 1; j <= m; j += 1) for (int k = i; k <= n; k += 1) for (int p = j; p <= m; p += 1) {
			if (get_sum(i, j, k, j) >= 1 && get_sum(i, p, k, p) >= 1 && get_sum(k, j, k, p) >= 1 && get_sum(i, j, i, p) >= 1) {
				answer = answer + (1LL << get_sum(i + 1, j + 1, k - 1, p - 1)) * (k - i + 1) * (p - j + 1);
			}
		}
		while (num_1 > 0 && answer > 0LL && answer % 2 == 0) {
			num_1 -= 1;
			answer /= 2LL;
		}
		cout << answer << '/' << (1LL << num_1) << '\n';
	}
	return 0;
}