제출 #332219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332219		vitkishloh228	Bomb (IZhO17_bomb)	C++14	14 / 100	957 ms	35976 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] - 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 = 1, tr = m + 1;
    while (tl < tr - 1) {
        int tm = (tl + tr) >> 1;
        //tm = 2;
        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;
                }
            }
        }*/
        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 << endl;
                            ok = false;
                            break;
                        }
                        if (S == (maxlen * tm)) {
                            for (int k = i; k < i + maxlen; ++k) {
                                freeze[k] = tm - 1;
                            }
                            i += maxlen - 1;
                            continue;
                        }
                    }
                    else if (!freeze[i]){
                        ok = 0;
                        break;
                    }

                    freeze[i]--;
                }
   
            }
        }
        if (ok) {
            //cout << "YES";
            tl = tm;
        }
        else tr = tm;
       
    }
    cout << (maxlen * tl);
}

• Subtask 1: 14 / 100