Submission #907294

#	Time	Username	Problem	Language	Result	Execution time	Memory
907294		daoquanglinh2007	Bomb (IZhO17_bomb)	C++17	41 / 100	1101 ms	55888 KiB

bomb

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

const int NM = 2500;

int N, M, f[NM+5][NM+5], dp[NM+5][NM+5], ans = 0;
char a[NM+5][NM+5];

int getf(int x, int y, int u, int v){
	return f[u][v]-f[x-1][v]-f[u][y-1]+f[x-1][y-1];
}

bool check(int r, int c){
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++) dp[i][j] = 0;
	
	for (int i = 1; i+r-1 <= N; i++)
		for (int j = 1; j+c-1 <= M; j++)
			if (getf(i, j, i+r-1, j+c-1) == r*c){
				dp[i][j]++;
				dp[i+r][j]--;
				dp[i][j+c]--;
				dp[i+r][j+c]++;
			}
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++){
			dp[i][j] += dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
			if (dp[i][j] == 0 && a[i][j] == '1') return 0;
		}
	return 1;
}

int main(){
//	freopen("BOMB.inp", "r", stdin);
//	freopen("BOMB.ans", "w", stdout);
	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];
			if (a[i][j] == '1') f[i][j] = 1;
		}
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			f[i][j] += f[i][j-1]+f[i-1][j]-f[i-1][j-1];
			
	int j = M;
	for (int i = 1; i <= N; i++){
		while (j >= 0 && !check(i, j)){
			j--;
			if (i*j <= ans) break;
		}
		ans = max(ans, i*j);
	}
	cout << ans;
	return 0;
}

• Subtask 1: 41 / 100