Submission #168966

#TimeUsernameProblemLanguageResultExecution timeMemory
168966abilBomb (IZhO17_bomb)C++14
10 / 100
1089 ms105712 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]; 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++){ if(a[i][j] == '1'){ if(up[i][j] + down[i][j] - 1 < x || leftt[i][j] + rightt[i][j] - 1 < y){ return false; } } } } return true; } bool check(int x){ bool f = false; for(int i = 1;i * i <= x; i++){ if(x % i == 0){ if(solve(x / i, i) || solve(i, x / i)){ f = true; break; } } } return f; } main() { cin >> n >> m; for(int i = 1;i <= n; i++){ for(int j = 1;j <= m; j++){ cin >> a[i][j]; } } 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; } } 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; } } 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; } } 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 l = 1, r = n * m; while(r - l > 1){ int mid = (r + l) >> 1; if(check(mid)){ l = mid; } else{ r = mid; } } if(check(r)){ l = r; } cout << l; }

Compilation message (stderr)

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