Submission #898941

#	Time	Username	Problem	Language	Result	Execution time	Memory
898941		hentai_lover	Bomb (IZhO17_bomb)	C++14	21 / 100	123 ms	62296 KiB

bomb

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <malloc.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& p) {in >> p.first >> p.second; return in;}
template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2>& p) {out << p.first << ' ' << p.second; return out;}
template<typename T> istream& operator>>(istream& in, vector<T>& v) {for (auto& x : v) in >> x; return in;}
template<typename T> ostream& operator<<(ostream& out, vector<T>& v) {for (auto& x : v) out << x << ' '; return out;}
template<typename T> ostream& operator<<(ostream& out, set<T>& v) {for (auto& x : v) out << x << ' '; return out;}
template<typename T> ostream& operator<<(ostream& out, multiset<T>& v) {for (auto& x : v) out << x << ' '; return out;}

const int MAX_INT = 2147483647;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<char>> f(n, vector<char>(m));
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> f[i][j];


    vector<vector<int>> up(n, vector<int>(m)), down(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (f[i][j] == '0') {
                up[i][j] = i;
            } else {
                up[i][j] = (i - 1 >= 0 ? up[i - 1][j] : i - 1);
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            if (f[i][j] == '0') {
                down[i][j] = i;
            } else {
                down[i][j] = (i + 1 < n ? down[i + 1][j] : i + 1);
            }
        }
    }

    int mx_y = 1e9;
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            int mn = 1e9;
            if (f[i][j] == '0') continue;

            int r = i;
            while (r + 1 < n && f[r + 1][j] == '1') r++;

            mn = min(mn, r - i + 1);

            i = r;
            mx_y = min(mx_y, mn);
        }
    }

    vector<ll> best(m + 1, mx_y);
    int mx_x = 1e9;
    for (int i = 0; i < n; i++) {
        int mn = 1e9;
        for (int j = 0; j < m; j++) {
            if (f[i][j] == '0') continue;

            int r = j;
            while (r + 1 < m && f[i][r + 1] == '1') r++;

            mn = min(mn, r - j + 1);

            int u = -1;
            int d = n;
            for (int id = j, len = 1; id <= r; id++, len++) {
                u = max(u, up[i][id]);
                d = min(d, down[i][id]);
            }
            for(int id = j, len = 1; id <= r; id ++, len ++){
                best[len] = min<ll>(best[len], d - u - 1);
            }

            j = r;
        }
        mx_x = min(mx_x, mn);
    }

    ll ans = 0;
    for (int i = 1; i <= mx_x; i++) ans = max(ans, i * best[i]);
    cout << ans << '\n';

    return 0;
}

• Subtask 1: 21 / 100