Submission #832311

#	Time	Username	Problem	Language	Result	Execution time	Memory
832311		vjudge1	Bomb (IZhO17_bomb)	C++14	16 / 100	1098 ms	55564 KiB

bomb

#include<bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll long long
#define rep(i,n,N) for(int i = n; i<=N; ++i)
#define rap(i,n,N) for(int i = n; i>=N; --i)
#define For(i,n,N) for(int i = n; i< N; ++i)
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define mems(x,y) memset(x,y,sizeof x)
#define ari(x) array<int,x>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fi first
#define se second
const int MAX = 2500 + 5;
mt19937 rng(time(NULL));

int n,m,mnr,mnc,cnt,y[MAX][MAX],z[MAX][MAX],ans,res;
char c;
bool x[MAX][MAX];
vector<ari(3)> v;

inline int fr(int k){
	int ret = n;
	rep(j,k,m){
		rep(i,1,n){
			if(z[i][j]-z[i][j-k]==k)++cnt;
			else if(cnt)ret = min(ret, cnt), cnt = 0;
		}
		if(cnt)ret = min(ret, cnt), cnt = 0;
	}
	return ret;
}

inline int fc(int k){
	int ret = m;
	rep(i,k,n){
		rep(j,1,m){
			if(y[i][j]-y[i-k][j]==k)++cnt;
			else if(cnt)ret = min(ret, cnt), cnt = 0;
		}
		if(cnt)ret = min(ret, cnt), cnt = 0;
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	mnr = n, mnc = m;
	rep(i,1,n){
		rep(j,1,m){
			cin>>c;
			x[i][j] = c=='1';
			y[i][j] = y[i-1][j]+x[i][j];
			z[i][j] = z[i][j-1]+x[i][j];
			if(x[i][j])++cnt;
			else if(cnt)mnc = min(mnc, cnt), cnt = 0;
		}
		if(cnt)mnc = min(mnc, cnt), cnt = 0;
	}
	rep(j,1,m){
		rep(i,1,n){
			if(x[i][j])++cnt;
			else if(cnt)mnr = min(mnr, cnt), cnt = 0;
		}
		if(cnt)mnr = min(mnr, cnt), cnt = 0;
	}
	int r = 1, c = mnc;
	ans = max(mnr, mnc);
	while(c > 1){
		while(r<=mnr && r*c<=ans)++r;
		if(r>mnr)break;
		
		res = fr(c);
		ans = max(ans, res*c);
		r = res+1;
		
		res = fc(r);
		ans = max(ans, res*r);
		c = res-1;
	}
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 16 / 100