제출 #666555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666555		Kaztaev_Alisher	Bomb (IZhO17_bomb)	C++17	16 / 100	1092 ms	37104 KiB

bomb

//#pragma GCC optomize ("Ofast")
//#pragma GCC optomize ("unroll-loops")
//#pragma GCC target ("avx,avx2,fma")
 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define sz size
#define cl clear
#define ins insert
#define ers erase
#define pii pair < int , int >
#define pll pair< long long  , long long >
#define all(x) x.begin() , x.end()
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define tostr(x) to_string(x)
#define tonum(s) atoi(s.c_str())
#define seon(x) setprecision(x)
#define bpop(x) __builtin_popcount(x)
#define deb(x) cerr << #x  << " = " << x << endl;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
const double PI = 3.14159265;
 
const ll N = 2500+5;
const ll mod = 1e9+7;
const ll inf = 1e9;
const ll INF = 1e18;
 
using namespace std;
 
char c[N][N];
int dp[N][N];
int n , m;
 
bool check(int x, int y){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(c[i][j] == 0) continue;
			bool ok = 0;
			for(int i1 = max(1, i-x+1); i1 <= i; i1++){
				for(int j1 = max(1 , j-y+1); j1 <= j; j1++){
					int cnt = dp[min(i1+x-1 , n)][min(j1+y-1 , m)] - dp[i1-1][min(j1+y-1 , m)] - dp[min(i1+x-1 , n)][j1-1] + dp[i1-1][j1-1];
					if(cnt == x*y) ok = 1;
				}	
			}
			if(ok == 0) return 0;
		}
	}
	return 1;
}
void solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> c[i][j];
			c[i][j] -= '0';
			dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + c[i][j];
		}
	}
	int ans = 0;
	for(int l = 1, r = n*m; l <= r;){
		int md = (l+r) >> 1;
		bool ok = 0;
		for(int i = 1; i <= sqrt(md); i++){
			if(md % i == 0){
				int j = md/i;
				if(check(i,j)) ans = max(ans , i*j) , ok = 1;
				if(check(j,i)) ans = max(ans , i*j) , ok = 1;
			}
		}
		if(ok == 1) l = md+1;
		else r = md-1;
	}
	cout << ans <<"\n";
}
signed main(){
//	file("bomb");
	ios;
	solve();
	return 0;
}
/*
*/ 

• Subtask 1: 16 / 100