제출 #832673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832673		vjudge1	Bomb (IZhO17_bomb)	C++14	97 / 100	621 ms	55552 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];
			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;
	}
	if(solve(mnr, mnc))return cout<<mnr*mnc<<endl,0;
	if(n*m > 2e6){
		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;
	}
	ans = mnc;
	rep(i,2,mnr){
		while(i*mnc>ans && !solve(i, mnc))--mnc;
		ans = max(ans, i*mnc);
	}
	cout<<ans<<endl;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 97 / 100