Submission #341001

#	Time	Username	Problem	Language	Result	Execution time	Memory
341001		Tosic	Bomb (IZhO17_bomb)	C++14	87 / 100	181 ms	80244 KiB

bomb

#include <bits/stdc++.h>
#define maxn 2510
using namespace std;

int n, m, ans, dp[maxn];
int a[maxn][maxn], up[maxn][maxn], down[maxn][maxn];

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; ++i){
		dp[i+1] = 1e9;
		for(int j = 0; j < m; ++j){
			char tmpC;
			cin >>tmpC;
			a[i][j] = tmpC-'0';
		}
	}
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			if(a[i][j]){
				up[i][j] = 1;
				if(i){
					up[i][j] += up[i-1][j];
				}
			}
		}
	}
	int tmp=n;
	for(int i = n-1; i >= 0; --i){
		for(int j = 0; j < m; ++j){
			if(a[i][j]){
				down[i][j] = 1 + down[i+1][j];
			}
		}
	}
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			if(!a[i][j]){
				continue;
			}
			int frJ = j, ln = 1, maxUp = up[i][j], maxD = down[i][j];
			dp[1] = min(dp[1], maxUp+maxD-1);
			while(a[i][j+1]){
				++j;
				++ln;
				maxUp = min(maxUp, up[i][j]);
				maxD = min(maxD, down[i][j]);
				dp[ln] = min(dp[ln], maxUp+maxD-1);

			}
			maxUp = 1e9, maxD = 1e9;
			ln = 1;
			for(int k = j; k >= frJ; --k){
				maxD = min(maxD, down[i][k]);
				maxUp = min(maxUp, up[i][k]);
				dp[ln] = min(dp[ln], maxUp+maxD-1);
				++ln;
			}
			tmp = min(tmp, abs(frJ-j)+1);
		}
	}
	for(int i = 1; i <= tmp; ++i){
		ans = max(ans, i*dp[i]);
	}
	cout << ans;
}

• Subtask 1: 87 / 100