제출 #1161850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161850		PieArmy	Bomb (IZhO17_bomb)	C++20	37 / 100	101 ms	25192 KiB

bomb

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

int n,m;
int table[2523][2523],mx[2523];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m;
	for(int &x:mx)
		x=n;
	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[table[i][j-1]+1]=0;
			}
		}
		if(table[i][m]){
			mx[table[i][m]+1]=0;
		}
	}
	for(int j=1;j<=m;j++){
		vector<pair<int,int>>v;
		for(int i=n+1;i>=1;i--){
			while(v.size()&&v.back().first>=table[i][j]){
				mx[v.back().first+1]=min(mx[v.back().first+1],v.back().second-i-1);
				v.pop_back();
			}
			if(table[i][j]<table[i-1][j]){
				v.push_back({table[i][j],i});
			}
		}
		if(table[1][j])while(v.size()){
			mx[v.back().first+1]=min(mx[v.back().first+1],v.back().second-1);
			v.pop_back();
		}
		v.clear();
		for(int i=0;i<=n;i++){
			while(v.size()&&v.back().first>=table[i][j]){
				mx[v.back().first+1]=min(mx[v.back().first+1],i-v.back().second-1);
				v.pop_back();
			}
			if(table[i][j]<table[i+1][j]){
				v.push_back({table[i][j],i});
			}
		}
		if(table[n][j])while(v.size()){
			mx[v.back().first+1]=min(mx[v.back().first+1],n-v.back().second);
			v.pop_back();
		}
		v.clear();
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		mx[i]=min(mx[i],mx[i-1]);
		ans=max(ans,mx[i]*i);
	}
	cout<<ans;
}

• Subtask 1: 37 / 100