Submission #332254

#	Time	Username	Problem	Language	Result	Execution time	Memory
332254		vitkishloh228	Bomb (IZhO17_bomb)	C++14	23 / 100	1102 ms	48464 KiB

bomb

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<queue>
using namespace std;
int solve1(int n, int m, vector<string> s) {
    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] - pr[i][j];
        }
    }
    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 + 100;
    while (tl < tr - 1) {
        int tm = (tl + tr) >> 1;
        //tm = 2;
        bool ok = true;
        vector<int> freeze(n);
        for (int j = 0; j < m; ++j) {

            if (!ok) break;
            for (int i = 0; i < n; ++i) {
                if (s[i][j] == '1') {
                    if (i + maxlen <= n && j + tm <= m) {
                        int S = pr[i + maxlen][j + tm] + pr[i][j] - pr[i + maxlen][j] - pr[i][j + tm];
                        if (S != (maxlen * tm) && !freeze[i]) {
                            //              cout << i << ' ' << j << ' '<<tm << endl;
                            ok = false;
                            break;
                        }
                        if (S == (maxlen * tm)) {
                            for (int k = i; k < i + maxlen; ++k) {
                                freeze[k] = tm;
                            }
                            //i += maxlen - 1;
                            //continue;
                        }
                    }
                    else if (!freeze[i]) {
                        //        cout << i << ' ' << j << ' ' << tm << endl;
                        ok = 0;
                        break;
                    }

                    freeze[i]--;
                }

            }
        }
        if (ok) {
            //cout << "YES";
            tl = tm;
        }
        else tr = tm;
    }
    return (maxlen * tl);
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0; i < n; ++i) cin >> s[i];
    int q1 = solve1(n, m, s);
    vector<string> r(m, string(n, '0'));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            r[j][i] = s[i][j];
        }
    }
    int q2 = solve1(m, n, r);
    cout << max(q1, q2);
}

• Subtask 1: 23 / 100