Submission #1134067

#TimeUsernameProblemLanguageResultExecution timeMemory
1134067MuhammetBomb (IZhO17_bomb)C++17
8 / 100
426 ms104608 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 2505;

int n, m, a[N][N], b[N][N], c[N][N], d[N][N], f[N];

char e[N][N];

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> e[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(e[i][j] == '1'){
				a[i][j] = a[i][j-1] + 1;
			}
			else {
				a[i][j] = 0;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = m; j >= 1; j--){
			if(e[i][j] == '1'){
				b[i][j] = b[i][j+1] + 1;
			}
			else {
				b[i][j] = 0;
			}
		}
	}
	for(int j = 1; j <= m; j++){
		for(int i = 1; i <= n; i++){
			if(e[i][j] == '1'){
				c[i][j] = c[i-1][j] + 1;
			}
			else {
				c[i][j] = 0;
			}
		}
	}
	for(int j = 1; j <= m; j++){
		for(int i = n; i >= 1; i--){
			if(e[i][j] == '1'){
				d[i][j] = d[i+1][j] + 1;
			}
			else {
				d[i][j] = 0;
			}
		}
	}
	memset(f, -1, sizeof f);
	int n1 = m;
	for(int i = 1; i <= n; i++){
		int cnt = 0, up = 0, dw = 0;
		for(int j = 1; j <= m; j++){
			if(e[i][j] == '1') n1 = min(n1, a[i][j] + b[i][j] - 1);
			if(e[i][j] == '0'){
				cnt = 0;
				up = dw = N;
				continue;
			}
			up = min(up, c[i][j]);
			dw = min(dw, d[i][j]);
			cnt++;
			if(~f[cnt-1]) f[cnt] = min(f[cnt-1], f[cnt]);
			if(~f[cnt]) f[cnt] = min(f[cnt], up+dw-1);
			else f[cnt] = up+dw-1;
		}
		cnt = 0, up = 0, dw = 0;
		for(int j = m; j >= 1; j--){
			if(e[i][j] == '0'){
				cnt = 0;
				up = dw = N;
				continue;
			}
			up = min(up, c[i][j]);
			dw = min(dw, d[i][j]);
			cnt++;
			if(~f[cnt+1]) f[cnt] = min(f[cnt+1], f[cnt]);
			if(~f[cnt]) f[cnt] = min(f[cnt], up+dw-1);
			else f[cnt] = up+dw-1;
		}
	}
	int ans = 0;
	for(int i = 1; i <= n1; i++){
		ans = max(ans, i*f[i]);
	}
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...