Submission #1161551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161551		PieArmy	Bomb (IZhO17_bomb)	C++20	38 / 100	872 ms	147428 KiB

bomb

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

#define int ll

int n,m;
int table[2502][2502],pref[2502][2502];
ll 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;
}

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;cin>>c;
			table[i][j]=c-'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: 38 / 100