Submission #1161990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161990		PieArmy	Bomb (IZhO17_bomb)	C++20	90 / 100	347 ms	74664 KiB

bomb

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

int n,m;
int table[2523][2523],ust[2523][2523],alt[2523][2523],mx;
int mn[2523];
int ans=0;

void cal(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(table[i][j]!=0&&table[i][j-1]==0){
				int a=ust[i][j],b=alt[i][j];
				for(int l=j;l<=m;l++){
					if(table[i][l]==0)break;
					a=max(a,ust[i][l]);
					b=min(b,alt[i][l]);
					mn[l-j+1]=min(mn[l-j+1],b-a+1);
				}
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m;
	for(int &x:mn)
		x=n;
	mx=m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;cin>>c;
			table[i][j]=c-'0';
			if(table[i][j]){
				table[i][j]=table[i][j-1]+1;
			}
			else if(table[i][j-1])mx=min(mx,table[i][j-1]);
		}
		if(table[i][m])mx=min(mx,table[i][m]);
	}
	for(int j=1;j<=m;j++){
		int x=n;
		for(int i=1;i<=n;i++){
			if(table[i-1][j]==0){
				ust[i][j]=i;
			}
			else ust[i][j]=ust[i-1][j];
			//if(table[i][j]&&table[i+1][j]==0)x=min(x,i-ust[i][j]+1);
		}
		for(int i=n;i>=1;i--){
			if(table[i+1][j]==0){
				alt[i][j]=i;
			}
			else alt[i][j]=alt[i+1][j];
		}
		for(int i=1;i<=mx;i++){
			mn[i]=min(mn[i],x);
		}
	}
	cal();
	for(int i=1;i<=n;i++){
		reverse(table[i]+1,table[i]+m+1);
		reverse(ust[i]+1,ust[i]+m+1);
		reverse(alt[i]+1,alt[i]+m+1);
	}
	cal();
	for(int i=1;i<=mx;i++){
		ans=max(ans,i*mn[i]);
	}
	cout<<ans;
}

• Subtask 1: 90 / 100