Submission #99837

#	Time	Username	Problem	Language	Result	Execution time	Memory
99837		naoai	Bomb (IZhO17_bomb)	C++14	24 / 100	242 ms	122532 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;

int n, m;
int v[nmax + 1][nmax + 1];
int u[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;

    int hmax = n + 1;
    int wmax = m + 1;

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

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

        s[i] += '0';
        for (int j = 0; j <= m; ++ j) {
            if (j > 0)
                if (s[i][j] == '0' && s[i][j - 1] == '1')
                    wmax = min(wmax, a);

            if (s[i][j] == '1')
                ++ a;
            else
                a = 0;
        }
    }

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

    for (int j = 0; j < m; ++ j) {
        int a = 0;
        for (int i = 1; i <= n + 1; ++ i) {
            if (i > 1)
                if (s[i][j] == '0' && s[i - 1][j] == '1')
                    hmax = min(hmax, a);

            if (s[i][j] == '1')
                ++ a;
            else
                a = 0;
        }
    }

    cout << wmax * hmax << "\n";
    check(hmax, wmax);

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 24 / 100