제출 #833869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833869		vjudge1	Bomb (IZhO17_bomb)	C++14	37 / 100	247 ms	2728 KiB

bomb

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

const int MAX = 450 + 5;

int n,m,x[MAX][MAX],pf[MAX][MAX],atk[MAX][MAX];
char c;

int get(int x1,int y1,int x2,int y2){
	x1--, y1--;
	return pf[x2][y2] - pf[x2][y1] - pf[x1][y2] + pf[x1][y1];
}

bool bisa(int h,int w){
	memset(atk, 0, sizeof atk);
	for(int i = h; i<=n; i++){
		for(int j = w; j<=m; j++){
			if(get(i-h+1, j-w+1, i, j) == h*w){
				atk[i-h+1][j-w+1]++;
				atk[i-h+1][j+1]--;
				atk[i+1][j-w+1]--;
				atk[i+1][j+1]++;
			}
		}
	}
	for(int i = 1; i<=n; i++){
		for(int j = 1; j<=m; j++){
			atk[i][j] = atk[i-1][j] + atk[i][j-1] - atk[i-1][j-1] + atk[i][j];
			if(atk[i][j]){
				if(!x[i][j])return false;
			}
			else {
				if(x[i][j])return false;
			}
		}
	}
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	if(max(n,m)>450)return 1;
	
	for(int i = 1; i<=n; i++){
		for(int j = 1; j<=m; j++){
			cin>>c;
			x[i][j] = (c=='1');
			pf[i][j] = pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1] + x[i][j];
		}
	}
	
//	bisa(3, 1);
//	
//	for(int i = 1; i<=n; i++){
//		for(int j = 1; j<=m; j++){
//			cout<<atk[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	
	int ans = 0;
	int w = m;
	for(int h = 1; h<=n; h++){
		while(w && !bisa(h,w))w--;
		ans = max(ans, h*w);
	}
	
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 37 / 100