Submission #55459

#	Time	Username	Problem	Language	Result	Execution time	Memory
55459		BThero	Bomb (IZhO17_bomb)	C++17	55 / 100	397 ms	132096 KiB

bomb

// Why I am so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;
                    
int up[2505][2505];

int dw[2505][2505];

char s[2505][2505];

int f[2505];

int n, m, ans;

void solve() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) {
        scanf("%s", s[i] + 1);
    }

    int limh = n, limw = m;

    for (int i = 1; i <= n; ++i) {
        int cur = 0;

        for (int j = 1; j <= m; ++j) {
            if (s[i][j] == '1') {
                ++cur;

                if (j == m || s[i][j + 1] == '0') {
                    limw = min(limw, cur);
                }
            }   
            else {
                cur = 0;
            }
        }    
    }

    for (int j = 1; j <= m; ++j) {
        int cur = 0;

        for (int i = 1; i <= n; ++i) {
            if (s[i][j] == '1') {
                up[i][j] = ++cur;

                if (i == n || s[i + 1][j] == '0') {
                    limh = min(limh, cur);
                }
            }
            else {
                cur = 0;
            }
        }
    }

    for (int j = 1; j <= m; ++j) {
        int cur = 0;

        for (int i = n; i > 0; --i) {
            if (s[i][j] == '1') {
                dw[i][j] = ++cur;
            }
            else {
                cur = 0;
            }
        }
    }

    for (int i = 1; i <= limw; ++i) {
        f[i] = limh;
    }

    for (int i = 1; i <= n; ++i) {
        int cur = 0, l = 100000, r = 100000;

        for (int j = 1; j <= m; ++j) {
            if (s[i][j] == '1') {
                ++cur;

                l = min(l, up[i][j]);
                r = min(r, dw[i][j]);

                f[cur] = min(f[cur], l + r - 1);
            }
            else {
                cur = 0;
                l = r = 100000;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        int cur = 0, l = 100000, r = 100000;

        for (int j = m; j > 0; --j) {
            if (s[i][j] == '1') {
                ++cur;

                l = min(l, up[i][j]);
                r = min(r, dw[i][j]);

                f[cur] = min(f[cur], l + r - 1);
            }
            else {
                cur = 0;
                l = r = 100000;
            }
        }
    }

    ans = f[1];                    

    for (int i = 2; i <= limw; ++i) {
        f[i] = min(f[i], f[i - 1]);
        ans = max(ans, i * f[i]);
    }

    printf("%d\n", ans);
}

int main() {
    //freopen("bomb.in", "r", stdin);
    //freopen("bomb.out", "w", stdout);
          
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'void solve()':
bomb.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
bomb.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s[i] + 1);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 55 / 100