Submission #833244

#	Time	Username	Problem	Language	Result	Execution time	Memory
833244		vjudge1	Bomb (IZhO17_bomb)	C++14	90 / 100	532 ms	55560 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;
char c;
bool x[MAX][MAX];
vector<ari(3)> v;

inline bool cek(int r,int c,int dr,int dc){
	return y[r][c] - y[r-dr][c] - y[r][c-dc] + y[r-dr][c-dc] == dr*dc;
}

inline bool solve(int dr,int dc){
	rep(i,1,n)mems(z[i], 0);
	rep(i,dr,n)rep(j,dc,m)if(x[i][j] && cek(i,j,dr,dc)){
		z[i][j]++;
		z[i-dr][j]--;
		z[i][j-dc]--;
		z[i-dr][j-dc]++;
	}
	rap(i,n,1)rap(j,m,1){
		z[i][j]+= z[i+1][j]+z[i][j+1]-z[i+1][j+1];
		if((!!z[i][j])!=x[i][j])return 0;
	}
	return 1;
}

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]+y[i][j-1]-y[i-1][j-1]+x[i][j];
		}
	}
	int k = min(mnr, mnc);
	int le,ri,mid;
	le = 1, ri = k;
	while(le<=ri){
		mid = le+ri>>1;
		if(solve(mid, mid))k = mid, le = mid+1;
		else ri = mid-1;
	}
	int r,c;
	r = c = k;
	if(r+1<=mnr && solve(r+1, c)){
		++r;
		le = r+1, ri = mnr;
		while(le<=ri){
			mid = le+ri>>1;
			if(solve(mid, c))r = mid, le = mid+1;
			else ri = mid-1;
		}
	}
	else if(c+1<=mnc){
		le = c+1, ri = mnc;
		while(le<=ri){
			mid = le+ri>>1;
			if(solve(r, mid))c = mid, le = mid+1;
			else ri = mid-1;
		}
	}
	cout<<r*c<<endl;
	return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:62:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |   mid = le+ri>>1;
      |         ~~^~~
bomb.cpp:72:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |    mid = le+ri>>1;
      |          ~~^~~
bomb.cpp:80:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |    mid = le+ri>>1;
      |          ~~^~~

• Subtask 1: 90 / 100