Submission #556160

#	Time	Username	Problem	Language	Result	Execution time	Memory
556160		ngpin04	Bomb (IZhO17_bomb)	C++14	90 / 100	274 ms	74444 KiB

bomb

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 2505;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

int up[N][N];
int dn[N][N];
int a[N][N];
int mx[N];
int n,m;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		string str; cin >> str;
		for (int j = 1; j <= m; j++)
			a[i][j] = str[j - 1] - '0';
	}	

	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++) 
			if (a[i][j])
				up[i][j] = up[i - 1][j] + 1;

		for (int i = n; i >= 1; i--)
			if (a[i][j])
				dn[i][j] = dn[i + 1][j] + 1;
	}

	for (int i = 1; i <= m; i++)
		mx[i] = oo;

	for (int i = 1; i <= n; i++) 
	for (int t = 0; t < 2; t++) {

		for (int j = 1; j <= m; j++) if (a[i][j]) {
			int k = j;
			while (a[i][k])
				k++;

			int f = oo, g = oo;
			for (int it = j; it < k; it++) {
				mini(f, up[i][it]);
				mini(g, dn[i][it]);

				// cerr << i << " " << j << " " << it << " " << f << " " << g << "\n";
				mini(mx[it - j + 1], f + g - 1);
			}

			mini(mx[k - j + 1], 0);
			j = k;
		}

		reverse(a[i] + 1, a[i] + m + 1);
		reverse(dn[i] + 1, dn[i] + m + 1);
		reverse(up[i] + 1, up[i] + m + 1);
	}
	
	int ans = 0;
	for (int i = 1; i <= m; i++) {
		if (i > 1)
			mini(mx[i], mx[i - 1]);
		maxi(ans, i * mx[i]);
	}

	cout << ans;
	return 0;
}

• Subtask 1: 90 / 100