Submission #168981

#TimeUsernameProblemLanguageResultExecution timeMemory
168981abilBomb (IZhO17_bomb)C++14
22 / 100
1099 ms111352 KiB
#include <bits/stdc++.h> #define fr first #define sc second #define pb push_back #define mk make_pair #define all(s) s.begin(),s.end() //#define int long long using namespace std; const int N = (2500 + 12); const int mod = (1e9 + 7); const int INF = (0x3f3f3f3f); char a[N][N], b[N][N]; int up[N][N], down[N][N], leftt[N][N], rightt[N][N]; int n, m; bool solve(int x,int y){ for(int i = 1;i <= n; i++){ for(int j = 1;j <= m; j++){ b[i][j] = '0'; } } for(int i = 1;i <= n; i++){ for(int j = 1;j <= m; j++){ if(a[i][j] == '1' && i >= x && j >= y){ int cnt = 0; for(int k = i - x + 1; k <= i; k++){ for(int l = j - y + 1; l <= j; l++){ cnt += (a[k][l] == '1'); } } if(cnt == x * y){ for(int k = i - x + 1; k <= i; k++){ for(int l = j - y + 1; l <= j; l++){ b[k][l] = '1'; } } } } } } for(int i = 1;i <= n; i++){ for(int j = 1;j <= m; j++){ if(a[i][j] != b[i][j]){ return false; } } } return true; } main() { cin >> n >> m; for(int i = 1;i <= n; i++){ for(int j = 1;j <= m; j++){ cin >> a[i][j]; } } int mnx = INF, mny = INF; for(int i = 1;i <= n; i++){ int cnt = 0; for(int j = 1;j <= m; j++){ cnt = (a[i][j] == '0' ? 0 : cnt + 1); leftt[i][j] = cnt; mny = min(mny, leftt[i][j]); } } for(int i = 1;i <= n; i++){ int cnt = 0; for(int j = m;j >= 1; j--){ cnt = (a[i][j] == '0' ? 0 : cnt + 1); rightt[i][j] = cnt; mny = min(mny, rightt[i][j]); } } for(int i = 1;i <= m; i++){ int cnt = 0; for(int j = 1;j <= n; j++){ cnt = (a[j][i] == '0' ? 0 : cnt + 1); up[j][i] = cnt; mnx = min(mnx, up[j][i]); } } for(int i = 1;i <= m; i++){ int cnt = 0; for(int j = n;j >= 1; j--){ cnt = (a[j][i] == '0' ? 0 : cnt + 1); down[j][i] = cnt; } } int ans = 0; for(int i = 1;i <= n; i++){ for(int j = 1;j <= m; j++){ if(solve(i,j)){ ans = max(ans, i * j); } } } cout << ans; } /* 20 20 11111000000000000000 11111000000000000000 11111100000000000000 11111111111000000000 00000111111000000000 00000111111000000000 00000011111000000000 00000001111100000000 00000000111110000000 00000000111110000000 00000000111110000000 00000000111110000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 */

Compilation message (stderr)

bomb.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...