제출 #173147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173147		VEGAnn	Bomb (IZhO17_bomb)	C++14	34 / 100	1098 ms	78328 KiB

bomb

#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define PB push_back
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2510;
const int oo = 2e9;
int n, m, ans, a[N][N], mx = oo, pr[N][N], best[N], nt[N][N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("in.txt","r",stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++){
        char c; cin >> c;
        a[i][j] = (c == '1' ? 1 : 0);
    }

    for (int j = 1; j <= m; j++){
        for (int i = 1; i <= n; ){
            if (a[i][j] == 0)
                i++;
            else {
                int i1 = i;
                while (i1 <= n && a[i1][j] == 1)
                    i1++;
                mx = min(mx, i1 - i);
                i = i1;
            }
        }
    }

    if (mx == oo){
        cout << n * m;
        return 0;
    }

    fill(best, best + n + 1, oo);

    for (int i = 1; i <= n; i++){
        int pre = 0;
        for (int j = 1; j <= m; j++){
            if (a[i][j] == 0)
                pre = j;
            pr[i][j] = pre + 1;
        }

        pre = m + 1;
        for (int j = m; j > 0; j--){
            if (a[i][j] == 0)
                pre = j;
            nt[i][j] = pre - 1;
        }
    }

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
        int mn = oo, mn1 = oo;
        int MN = oo, MN1 = oo;
        bool bd1 = 0, bd2 = 0;
//        if (i == 5 && j == 5){
//            cerr << "OK\n";
//        }
        for (int h = 1; h <= mx; h++){
            int ii = i - h + 1;
            int i2 = i + h - 1;
            if (i < h) bd1 = 1;
            if (i + h - 1 > n) bd2 = 1;
            if (!bd1 && a[ii][j] == 0) bd1 = 1;
            if (!bd2 && a[i2][j] == 0) bd2 = 1;
            if (bd1 && bd2) break;

            int res = 0;
            if (!bd1){
                mn = min(mn, j - pr[ii][j] + 1);
                mn1 = min(mn1, nt[ii][j] - j);
                res = max(res, mn + mn1);
            }
            if (!bd2){
                MN = min(MN, j - pr[i2][j] + 1);
                MN1 = min(MN1, nt[i2][j] - j);
                res = max(res, MN + MN1);
            }
            best[h] = min(best[h], res);
        }
    }

    for (int i = 1; i <= mx; i++) {
        if (best[i] == oo) return -1;
        ans = max(ans, best[i] * i);
    }

    cout << ans << '\n';

    return 0;
}

• Subtask 1: 34 / 100