Submission #907385

#	Time	Username	Problem	Language	Result	Execution time	Memory
907385		daoquanglinh2007	Bomb (IZhO17_bomb)	C++17	100 / 100	216 ms	104688 KiB

bomb

#include <bits/stdc++.h>
using namespace std;
 
const int NM = 2500, inf = 1e9+7;
 
int N, M, Up[NM+5][NM+5], Down[NM+5][NM+5], Left[NM+5][NM+5], Right[NM+5][NM+5], H = +inf, W = +inf;
int mx[NM+5], ans = 0;
char a[NM+5][NM+5];

void preprocess(){
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			if (a[i][j] == '1'){
				Up[i][j] = Up[i-1][j]+1;
				Left[i][j] = Left[i][j-1]+1;
			}
	for (int i = N; i >= 1; i--)
		for (int j = M; j >= 1; j--)
			if (a[i][j] == '1'){
				Down[i][j] = Down[i+1][j]+1;
				Right[i][j] = Right[i][j+1]+1;
				
				H = min(H, Up[i][j]+Down[i][j]-1);
				W = min(W, Left[i][j]+Right[i][j]-1);
			}
			
	for (int i = 1; i <= H; i++) mx[i] = W;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> a[i][j];
			
	preprocess();
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++){
			if (Down[i][j] == 1){
				int l = -inf, r = +inf;
				for (int k = 1; k <= H; k++){
					if (i-k+1 < 1) continue;
					l = max(l, j-Left[i-k+1][j]+1);
					r = min(r, j+Right[i-k+1][j]-1);
					mx[k] = min(mx[k], r-l+1);
				}
			}
			if (Up[i][j] == 1){
				int l = -inf, r = +inf;
				for (int k = 1; k <= H; k++){
					if (i+k-1 > N) continue;
					l = max(l, j-Left[i+k-1][j]+1);
					r = min(r, j+Right[i+k-1][j]-1);
					mx[k] = min(mx[k], r-l+1);
				}
			}
		}
	for (int i = 1; i <= H; i++) ans = max(ans, i*mx[i]);
	cout << ans;
	return 0;
}

• Subtask 1: 100 / 100