Submission #87293

#TimeUsernameProblemLanguageResultExecution timeMemory
87293YaroslaffBomb (IZhO17_bomb)C++14
50 / 100
457 ms132096 KiB
#include <bits/stdc++.h> #define pb push_back #define F first #define S second #define ll long long #define int short int #define ld long double #define null nullptr #define endl '\n' using namespace std; mt19937 gen(chrono::system_clock::now().time_since_epoch().count()); //const int M = 1e9 + 7; const int N = 2502; int n, m, x[N][N], l[N][N], r[N][N], res[N], ans; string s[N]; main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); //#else // freopen("bomb.in","r",stdin); // freopen("bomb.out","w",stdout); #endif cin >> n >> m; for (int i = 0; i < n; i++){ cin >> s[i];res[i + 1] = N; for (int j = 0; j < m; j++) x[i][j] = s[i][j] - '0'; } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){ if (!x[i][j]) l[i][j] = 0; else l[i][j] = (j ? l[i][j - 1] : 0) + 1; } for (int i = n - 1; i >= 0; i--) for (int j = m - 1; j >= 0; j--){ if (!x[i][j]) r[i][j] = 0; else r[i][j] = r[i][j + 1] + 1; } for (int j = 0; j < m; j++){ int tl = N; int tr = N; int p = -1; for (int i = 0; i <= n; i++){ if (i != n && x[i][j] == 1){ res[1] = min(res[1], (int)(l[i][j] + r[i][j] - 1)); int len = i - p; tl = min(tl, l[i][j]); tr = min(tr, r[i][j]); res[len] = min(res[len], (int)(tl + tr - 1)); } if (i == n || x[i][j] == 0){ int l = i - p; // cerr << l << endl; if (l != 1) res[l] = 0; tl = tr = N; p = i; } } tl = N; tr = N; p = n; for (int i = n - 1; i >= -1; i--){ if (i != -1 && x[i][j] == 1){ res[1] = min(res[1], (int)(l[i][j] + r[i][j] - 1)); int len = p - i; tl = min(tl, l[i][j]); tr = min(tr, r[i][j]); res[len] = min(res[len], (int)(tl + tr - 1)); } if (i == -1 || x[i][j] == 0){ int l = p - i; // cerr << l << endl; if (l != 1) res[l] = 0; tl = tr = N; p = i; } } } for (int i = 2; i <= n; i++) res[i] = min(res[i], res[i - 1]); for (int i = 1; i <= n; i++) ans = max(ans, (int)(i*res[i])); cout << ans; return 0; }

Compilation message (stderr)

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