Submission #1134111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134111		Muhammet	Bomb (IZhO17_bomb)	C++17	52 / 100	278 ms	104620 KiB

bomb

#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(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	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 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 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 = n+1, m1 = m+1;
	for(int i = 1; i <= n; i++){
		int cnt = 0, up = N, dw = N;
		for(int j = 1; j <= m; j++){
			if(e[i][j] == '0'){
				cnt = 0, up = dw = N;
				continue;
			}
			n1 = min(n1, a[i][j] + b[i][j] - 1);
			m1 = min(m1, c[i][j] + d[i][j] - 1);
			up = min(up, c[i][j]);
			dw = min(dw, d[i][j]);
			cnt++;
			if(~f[cnt]) f[cnt] = min(f[cnt], up+dw-1);
			else f[cnt] = up+dw-1;
		}
		cnt = 0, up = N, dw = N;
		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]) f[cnt] = min(f[cnt], up+dw-1);
			else f[cnt] = up+dw-1;
		}
	}
	int ans = 0;
	if(m1 == m+1) m1 = 0;
	for(int i = 1; i <= m1; i++){
		f[i] = min(f[i], n1);
		ans = max(ans, i*f[i]);
	}
	cout << ans;
}

• Subtask 1: 52 / 100