Submission #332214

#	Time	Username	Problem	Language	Result	Execution time	Memory
332214		vitkishloh228	Bomb (IZhO17_bomb)	C++14	5 / 100	239 ms	40832 KiB

bomb

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    vector<vector<int>> pr(n + 1, vector<int>(m + 1));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int val = s[i][j] - '0';
            pr[i + 1][j + 1] = val + pr[i + 1][j] + pr[i][j + 1];
        }
    }
    int maxlen = n;
    for (int j = 0; j < m; ++j) {
        int L0 = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i][j] == '1') {
                L0++;
            }
            else {
                if (L0) {
                    maxlen = min(maxlen, L0);
                }
                L0 = 0;
            }
        }
        if (L0) {
            maxlen = min(maxlen, L0);
        }
    }
    int tl = 0, tr = m;
    while (tl < tr - 1) {
        int tm = (tl + tr) >> 1;
        bool ok = true;
        for (int i = 0; i < n - maxlen; ++i) {
            if (!ok) break;
            for (int j = 0; j < m - tm; ++j) {
                int S = pr[i + maxlen][j + tm] + pr[i][j] - pr[i + maxlen][j] - pr[i][j + tm];
                if (S != (maxlen * tm)) {
                    ok = false;
                    break;
                }
            }
        }
        if (ok) {
            tl = tm;
        }
        else tr = tm;
    }
    cout << (maxlen * tr);
}

• Subtask 1: 5 / 100