Submission #1134071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134071		Muhammet	Bomb (IZhO17_bomb)	C++17	90 / 100	419 ms	104608 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(){
	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 = N, dw = N;
		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]) 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;
	for(int i = 1; i <= n1; i++){
		ans = max(ans, i*f[i]);
	}
	cout << ans;
}

• Subtask 1: 90 / 100