제출 #832220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832220		vjudge1	Bomb (IZhO17_bomb)	C++14	24 / 100	178 ms	118128 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(99);

int n,m,mnr,mnc,cnt,y[MAX][MAX],z[MAX][MAX];
char c;
bool x[MAX][MAX];

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;
}

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;
	}
	rep(i,mnr,n)rep(j,mnc,m)if(x[i][j] && cek(i,j,mnr,mnc)){
		z[i][j]++;
		z[i-mnr][j]--;
		z[i][j-mnc]--;
		z[i-mnr][j-mnc]++;
	}
	rap(i,n,1)rap(j,m,1)z[i][j]+= z[i+1][j]+z[i][j+1]-z[i+1][j+1];
	rep(i,1,n){
//		if(i==1)cout<<"--------------\n";
//		rep(j,1,m)cout<<z[i][j];
//		cout<<endl;
		rep(j,1,m){
			assert((!!z[i][j])==x[i][j]);
		}
	}
	cout<<mnr*mnc<<endl;
	return 0;
}

• Subtask 1: 24 / 100