Submission #100306

#	Time	Username	Problem	Language	Result	Execution time	Memory
100306		naoai	Bomb (IZhO17_bomb)	C++14	100 / 100	603 ms	62716 KiB

bomb

#include <bits/stdc++.h>

using namespace std;

#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");

const int nmax = 2500 + 5;
const int inf = 1 << 30;

int n, m;
int v[nmax + 1][nmax + 1];
int u[nmax + 1][nmax + 1];

int w[nmax + 1];
int st[nmax + 1][nmax + 1], dr[nmax + 1][nmax + 1];
string s[nmax + 1];

void check (int h, int w) {
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            v[i][j] = v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1] + (s[i][j - 1] - '0');
        }
    }

    bool ok = 1;
    for (int i = 1; i <= n - h + 1; ++ i) {
        for (int j = 1; j <= m - w + 1; ++ j) {
            int sum = v[i + h - 1][j + w - 1] - v[i - 1][j + w - 1] - v[i + h - 1][j - 1] + v[i - 1][j - 1];
            if (sum == h * w) {
                ++ u[i][j];
                ++ u[i + h][j + w];
                -- u[i + h][j];
                -- u[i][j + w];
            }
        }
    }

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            u[i][j] += u[i - 1][j] + u[i][j - 1] - u[i - 1][j - 1];
            if ((u[i][j] == 0) != ((s[i][j - 1] - '0') == 0)) {
                assert(0);
            }
        }
    }
}

int main() {
    fin.sync_with_stdio(false); fin.tie(); fout.tie();
    fin >> n >> m;

    for (int i = 1; i <= n; ++ i)
        fin >> s[i];

    for (int i = 1; i <= n; ++ i) {
        s[i] = '0' + s[i] + '0';
    }

    s[0].resize(m + 2, '0');
    s[n + 1].resize(m + 2, '0');

    for (int i = 1; i <= n; ++ i) {
        st[i][0] = 1;
        for (int j = 1; j <= m; ++ j) {
            if (s[i][j] == '1')
                st[i][j] = st[i][j - 1];
            else
                st[i][j] = j + 1;
        }

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

    for (int i = 1; i <= n; ++ i)
        w[i] = inf;

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            if (s[i - 1][j] == '0' && s[i][j] == '1') {
                int k = i;
                int mn = st[i][j], mx = dr[i][j];

                while (k <= m && s[k][j] == '1') {
                    mn = max(mn, st[k][j]);
                    mx = min(mx, dr[k][j]);
                    w[k - i + 1] = min(w[k - i + 1], mx - mn + 1);
                    ++ k;
                }
            }
        }

        for (int j = 1; j <= m; ++ j) {
            if (s[i + 1][j] == '0' && s[i][j] == '1') {
                int k = i;
                int mn = st[i][j], mx = dr[i][j];

                while (k > 0 && s[k][j] == '1') {
                    mn = max(mn, st[k][j]);
                    mx = min(mx, dr[k][j]);
                    w[i - k + 1] = min(w[i - k + 1], mx - mn + 1);
                    -- k;
                }
            }
        }
    }

    int h = inf;
    for (int j = 1; j <= m; ++ j) {
        int cnt = 0;
        for (int i = 1; i <= n; ++ i) {
            if (s[i][j] == '1')
                ++ cnt;
            else
                cnt = 0;

            if (s[i][j] == '1' && s[i + 1][j] == '0')
                h = min(h, cnt);
        }
    }

    int _w = inf;
    for (int i = 1; i <= n; ++ i) {
        int cnt = 0;
        for (int j = 1; j <= m; ++ j) {
            if (s[i][j] == '1')
                ++ cnt;
            else
                cnt = 0;

            if (s[i][j] == '1' && s[i][j + 1] == '0')
                _w = min(_w, cnt);
        }
    }

    int amax = 0;
    for (int i = 1; i <= h; ++ i) {
        if (w[i] != inf)
            amax = max(amax, i * min(w[i], _w));
    }

    cout << amax << "\n";

    return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'void check(int, int)':
bomb.cpp:27:10: warning: unused variable 'ok' [-Wunused-variable]
     bool ok = 1;
          ^~

• Subtask 1: 100 / 100