제출 #1159421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159421		PieArmy	Bomb (IZhO17_bomb)	C++20	91 / 100	573 ms	73944 KiB

bomb

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

int n,m;
int table[2502][2502],pref[2502][2502],bomb[2502][2502];

bool f(int x,int y){
	for(int i=1;i<=n+1;i++){
		for(int j=1;j<=m+1;j++){
			bomb[i][j]=0;
		}
	}
	for(int i=1;i+x<=n+1;i++){
		for(int j=1;j+y<=m+1;j++){
			if(pref[i-1][j-1]+pref[i+x-1][j+y-1]==pref[i+x-1][j-1]+pref[i-1][j+y-1]){
				bomb[i][j]++;
				bomb[i+x][j]--;
				bomb[i][j+y]--;
				bomb[i+x][j+y]++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			bomb[i][j]+=bomb[i-1][j]+bomb[i][j-1]-bomb[i-1][j-1];
			if(bomb[i][j]==0&&table[i][j]!=0){
				return false;
			}
		}
	}
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		for(int j=1;j<=m;j++){
			table[i][j]=s[j-1]-'0';
			pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
			if(table[i][j]==0){
				pref[i][j]++;
			}
		}
	}
	int l=1,r=min(n,m);
	while(l<r){
		int mi=(l+r+1)/2;
		if(f(mi,mi))l=mi;
		else r=mi-1;
	}
	int kare=l,ans=kare*kare;
	l=kare;r=m;
	while(l<r){
		int mi=(l+r+1)/2;
		if(f(kare,mi))l=mi;
		else r=mi-1;
	}
	ans=max(ans,kare*l);
	l=kare;r=n;
	while(l<r){
		int mi=(l+r+1)/2;
		if(f(mi,kare))l=mi;
		else r=mi-1;
	}
	ans=max(ans,kare*l);
	cout<<ans;
}

• Subtask 1: 91 / 100