제출 #334568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334568		tengiz05	Bomb (IZhO17_bomb)	C++17	100 / 100	326 ms	87660 KiB

bomb

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2505;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N][N], n, m, k;
bool usedup[N][N], usedr[N][N];
int up[N][N], down[N][N];
int ans[N];
vector<int> v[N];
vector<int> s[N];
void solve(int test_case){
	int i, j;
	cin >> n >> m;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			char c;
			cin >> c;
			a[i][j] = (c-'0');
		}
	}
	int mx=mod, my=mod;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(a[i][j] == 1){
				if(usedup[i][j])continue;
				int t = j;
				int tmp = 0;
				while(t <= m && a[i][t] == 1){
					tmp++;
					usedup[i][t] = true;
					t++;
				}mx = min(mx, tmp);
			}
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(a[i][j] == 1){
				if(usedr[i][j])continue;
				int t = i;
				int tmp = 0;
				while(t <= n && a[t][j] == 1){
					tmp++;
					usedr[t][j] = true;
					t++;
				}my = min(my, tmp);
			}
		}
	}
	if(mx == mod){
		mx = 0;
		my = 0;
	}
	
	/// (mx, my) is greedy answer
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(a[i][j])up[i][j] = up[i-1][j]+a[i][j];
		}
	}
	for(i=n;i>=1;i--){
		for(j=1;j<=m;j++){
			if(a[i][j])down[i][j] = down[i+1][j]+a[i][j];
		}
	}
	
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(!a[i][j])continue;
			int cnt = 1;
			int tmp = j;
			while(j+1 <= m && a[i][j+1])cnt++,j++;
			v[i].pb(tmp);
			s[i].pb(cnt);
		}
	}
	for(i=1;i<=m;i++)ans[i] = my;
	for(i=1;i<=n;i++){
		for(k=0;k<v[i].size();k++){
			int j = v[i][k];
			int sz = s[i][k];
			int a=mod, b=mod, c=0;
			for(;sz;sz--, j++){
				a = min(a, up[i][j]);
				b = min(b, down[i][j]);
				c++;
				ans[c] = min(ans[c], a+b-1);
			}
		}
		
		for(k=(int)v[i].size()-1;k>=0;k--){
			int sz = s[i][k];
			int j = v[i][k]+sz-1;
			int a=mod, b=mod, c=0;
			for(;sz;sz--, j--){
				a = min(a, up[i][j]);
				b = min(b, down[i][j]);
				c++;
				ans[c] = min(ans[c], a+b-1);
			}
		}
		
	}
//	cout << mx << ' ' << my << '\n';
	for(i=2;i<=mx;i++)ans[i] = min(ans[i], ans[i-1]);
	int res = 0;
//	for(i=1;i<=mx;i++)cout << ans[i] << ' '; cout << '\n';
	for(i=1;i<=mx;i++)res = max(res, i*ans[i]);
	cout << res << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}
/*

6 6
000111
011111
011111
111000
111000
111000


*/

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

bomb.cpp: In function 'void solve(int)':
bomb.cpp:88:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(k=0;k<v[i].size();k++){
      |           ~^~~~~~~~~~~~

• Subtask 1: 100 / 100