Boj1451_직사각형으로 나누기

Published: by Creative Commons Licence

  • Tags:

boj1451_직사각형으로 나누기

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n, m, ans;
int arr[110][110],sum[110][110];

ll gA(ll sr, ll sc, ll er, ll ec) {
	if (sr > er || sc > ec) return 0;
	return (long long)sum[er][ec] - sum[sr - 1][ec] - sum[er][sc - 1] + sum[sr - 1][sc - 1];
}

ll gW(ll sr, ll sc, ll er, ll ec) {
	ll rs = 0;
	if (sr > er || sc > ec) return 0;
	for (ll i = sr; i <= er; i++) {
		if (i + 1 > er) continue;
		rs = max(rs, gA(sr, sc, i, ec)*gA(i + 1, sc, er, ec));
	}
	for (ll j = sc; j <= ec; j++) {
		if (j + 1 > ec) continue;
		rs = max(rs, gA(sr, sc, er, j)*gA(sr, j + 1, er, ec));
	}
	return rs;
}



int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &arr[i][j]);
			sum[i][j] += (long long)(arr[i][j] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1]);
		}
	}
	for (ll i = 1; i <= n; i++) {
		ans = max(ans, gA(1, 1, i, m)*gW(i + 1, 1, n, m));
		ans = max(ans, gA(i + 1, 1, n, m)*gW(1, 1, i, m));
	}
	for (ll i = 1; i <= m; i++) {
		ans = max(ans, gA(1, 1, n, i)*gW(1, i + 1, n, m));
		ans = max(ans, gA(1, i + 1, n, m)*gW(1, 1, n, i));
	}
	printf("%lld", ans);
}