제출 #833907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833907		vjudge1	Bomb (IZhO17_bomb)	C++17	52 / 100	273 ms	55436 KiB

bomb

#include <bits/stdc++.h>

using namespace std;

const int N = 2502;
bool grid[N][N];
int top[N][N], bot[N][N];   //indexing the 1's from top to bottom and vice versa
/*
STOP THINKING OF USING PREFIX SUM we need to know how many consecutive 1's yang ada di kolom yang sama if we take (i, j) pls i don't need to reimplement this 1e9 + 7 times ;-;

example:

111000
111000
111111
000111
000111

clearly we can't use prefix sum ok, we need to know how many 1's are in that group so we can use array top and bottom to help us. they'll store the index from top to bottom and vice versa. choosing (i, j) means that there are top[i][j] + bot[i][j] - 1 elements (exclude the middle point to avoid double counting)
*/

int maxH[N]; //if W = i, then what's the maximum H we can take?
int n, m;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char c; cin >> c;
            grid[i][j] = (c == '1');
        }
    }

    for(int j = 1; j <= m; j++){
        for(int i = 1; i <= n; i++){
            if(grid[i][j]) top[i][j] = top[i - 1][j] + 1;
        }

        for(int i = n; i >= 1; i--){
            if(grid[i][j]) bot[i][j] = bot[i + 1][j] + 1;
        }
    }
    
    int H = n, W = m;
    for(int i = 1; i <= n; i++){
        int cons = 0;
        for(int j = 1; j <= m; j++){
            if(grid[i][j]) cons++;
            else{
                if(cons > 0) W = min(W, cons);
                cons = 0;
            }
        }

        if(cons > 0) W = min(W, cons);
    }

    for(int j = 1; j <= m; j++){
        int cons = 0;
        for(int i = 1; i <= n; i++){
            if(grid[i][j]) cons++;
            else{
                if(cons > 0) H = min(H, cons);
                cons = 0;
            }
        }

        if(cons > 0) H = min(H, cons);
    }

    for(int i = 1; i <= W; i++) maxH[i] = H;

    for(int i = 1; i <= n; i++){
        int cur = 0, t = 1e9, b = 1e9;
        for(int j = 1; j <= m; j++){
            if(grid[i][j]){
                t = min(t, top[i][j]);
                b = min(b, bot[i][j]);
                cur++;
                //cout << ":: " << i << " " << j << " = " << cur << " = " << b + t - 1 << endl;
                maxH[cur] = min(maxH[cur], t+b-1);
            } else{
                t = b = 1e9;
                cur = 0;
            }
        }
    }


    int ans = 0;
    int mini = maxH[1];
    for(int i = 1; i <= W; i++){
        mini = min(mini, maxH[i]);
        ans = max(ans, i*mini);
    }

    cout << ans << '\n';

    return 0;
}

• Subtask 1: 52 / 100