제출 #833895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833895		vjudge1	Bomb (IZhO17_bomb)	C++14	91 / 100	647 ms	75232 KiB

bomb

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

const int MAX = 2500 + 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;
	
	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,h;
	
	int le,ri,mid,s;
	le = 2, ri = min(n,m);
	s = 1;
	while(le<=ri){
		mid = (le+ri)>>1;
		if(bisa(mid, mid))s = mid, le = mid+1;
		else ri = mid-1;
	}
	
	h = w = s;
	if(w+1<=m && bisa(h,w+1)){
		le = w+1, ri = m;
		while(le<=ri){
			mid = (le+ri)>>1;
			if(bisa(h, mid))w = mid, le = mid+1;
			else ri = mid-1;
		}
	}
	else if(h+1<=n){
		le = h+1, ri = n;
		while(le<=ri){
			mid = (le+ri)>>1;
			if(bisa(mid, w))h = mid, le = mid+1;
			else ri = mid-1;
		}
	}
	
	cout<<h*w<<endl;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bomb.cpp: In function 'int main()':
bomb.cpp:61:6: warning: unused variable 'ans' [-Wunused-variable]
   61 |  int ans = 0;
      |      ^~~

• Subtask 1: 91 / 100