Submission #223999

#	Time	Username	Problem	Language	Result	Execution time	Memory
223999		super_j6	Bomb (IZhO17_bomb)	C++14	100 / 100	370 ms	74012 KiB

bomb

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int maxn = 2500;
int n, m;
int a[maxn][maxn], u[maxn][maxn], d[maxn][maxn];
int dp[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++)
	for(int j = 0; j < m; j++){
		char c;
		cin >> c;
		a[i][j] = c - '0';
	}
	
	for(int j = 0; j < m; j++){
		dp[j] = n;
		u[n - 1][j] = n - 1;
		for(int i = 1; i < n; i++){
			d[i][j] = !a[i][j] || !a[i - 1][j] ? i : d[i - 1][j];
			u[n - i - 1][j] = !a[n - i - 1][j] || !a[n - i][j] ? n - i - 1 : u[n - i][j];
		}
	}
	
	for(int i = 0; i < n; i++)
	for(int j = 0, l = 0, ul = n - 1, dl = 0, r = m - 1, ur = n - 1, dr = 0; j < m; j++){
		if(a[i][j]){
			dp[0] = min(dp[0], u[i][j] - d[i][j] + 1);
			ul = min(ul, u[i][j]), dl = max(dl, d[i][j]);
			dp[j - l] = min(dp[j - l], ul - dl + 1);
		}else{
			if(j > l) dp[j - l] = 0;
			l = j + 1;
			ul = n - 1, dl = 0;
		}
		if(a[i][m - j - 1]){
			ur = min(ur, u[i][m - j - 1]), dr = max(dr, d[i][m - j - 1]);
			dp[r + j + 1 - m] = min(dp[r + j + 1 - m], ur - dr + 1);
		}else{
			if(m - j - 1 < r) dp[r + j + 1 - m] = 0;
			r = m - j - 2;
			ur = n - 1, dr = 0;
		}
	}
	
	int ret = 0;
	for(int i = 0; i < m; i++){
		if(i) dp[i] = min(dp[i], dp[i - 1]);
		ret = max(ret, (i + 1) * dp[i]);
	}
	
	cout << ret << endl;

	return 0;
}

• Subtask 1: 100 / 100