Sunday, June 14, 2015

UVa 10074 - Take the Land

// UVa 10074 - Take the Land

#include <iostream>
using namespace std;

int main() {

	int n, m;
	cin >> n >> m;

	while (n || m) {
		int bit, S[101][101];
		int sol = 0;
		// base cases
		for (int i = 0; i <= n; i++)
			S[i][0] = 0;
		for (int j = 0; j <= n; j++)
			S[0][j] = 0;
		// dp
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				cin >> bit;
				S[i][j] = (i > 0 ? S[i - 1][j] : 0) + (j > 0 ? S[i][j - 1] : 0) - (i > 0 && j > 0 ? S[i - 1][j - 1] : 0) + bit;
				for (int a = 0; a < i; a++)
					for (int b = 0; b < j; b++) {
						if (S[i][j] - S[a][j] - S[i][b] + S[a][b] == 0 && (i - a) * (j - b) > sol)
							sol = (i - a) * (j - b);
					}
			}
		cout << sol << endl;
		cin >> n >> m;
	}

	return 0;
}

No comments:

Post a Comment