Submission #855461

#TimeUsernameProblemLanguageResultExecution timeMemory
855461AlfraganusBomb (IZhO17_bomb)C++17
33 / 100
133 ms104952 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define fs first #define ss second #define all(a) a.begin(), a.end() #define print(a) \ for (auto x : a) \ cout << x << ' '; \ cout << endl; #define printmp(a) \ for (auto x : a) \ cout << x.fs << ' ' << x.ss << endl; void solve(){ int n, m; cin >> n >> m; vector<vector<char>> a(n, vector<char> (m)); for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) cin >> a[i][j]; if(n <= 20 and m <= 20){ int ans = 0; for(int i = 1; i <= n; i ++){ for(int j = 1; j <= m; j ++){ vector<vector<char>> b = a; for(int i1 = 0; i1 <= n - i; i1 ++){ for(int i2 = 0; i2 <= m - j; i2 ++){ if(b[i1][i2] != '0'){ bool flag = 1; for(int x = 0; x < i; x ++){ for(int y = 0; y < j; y ++){ if(b[i1 + x][i2 + y] == '0') flag = false; } } if(flag){ for(int x = 0; x < i; x ++){ for(int y = 0; y < j; y ++){ b[i1 + x][i2 + y] = '2'; } } } } } } int cnt = 0; for(int i = 0; i < n; i ++){ for(int j = 0; j < m; j ++){ cnt += b[i][j] == '1'; } } if(cnt == 0) ans = max(ans, i * j); } } cout << ans; return; } vector<vector<int>> dp_right(n, vector<int>(m)), dp_down(n, vector<int>(m)); for(int i = n - 1; i >= 0; i --){ for(int j = m - 1; j >= 0; j --){ if(a[i][j] == '1'){ dp_right[i][j] = (j == m - 1 ? 0 : dp_right[i][j + 1]) + 1; dp_down[i][j] = (i == n - 1 ? 0 : dp_down[i + 1][j]) + 1; } else{ dp_right[i][j] = 0; dp_down[i][j] = 0; } } } int x = m, y = n; for(int i = 0; i < n; i ++){ for(int j = 0; j < m; j ++){ if(a[i][j] == '1'){ if(j == 0 or a[i][j - 1] == '0') x = min(x, dp_right[i][j]); if(i == 0 or a[i - 1][j] == '0') y = min(y, dp_down[i][j]); } } } cout << x * y << endl; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); // freopen("bomb.in", "r", stdin); // freopen("bomb.out", "w", stdout); int t = 1; // cin >> t; while(t --){ solve(); cout << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...