oj.uz

답안 #833907

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
833907 2023-08-22T09:27:34 Z vjudge1 Bomb (IZhO17_bomb) C++17
52 / 100
 273 ms 55436 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 9 ms 26508 KB Output is correct
4 Correct 9 ms 26452 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 0 ms 468 KB Output isn't correct
9 Incorrect 0 ms 468 KB Output isn't correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Incorrect 1 ms 468 KB Output isn't correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Incorrect 0 ms 468 KB Output isn't correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 1 ms 1060 KB Output is correct
18 Correct 1 ms 724 KB Output is correct
19 Incorrect 1 ms 980 KB Output isn't correct
20 Incorrect 1 ms 980 KB Output isn't correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 724 KB Output is correct
23 Incorrect 1 ms 980 KB Output isn't correct
24 Incorrect 1 ms 980 KB Output isn't correct
25 Incorrect 1 ms 1236 KB Output isn't correct
26 Correct 1 ms 1364 KB Output is correct
27 Correct 3 ms 3924 KB Output is correct
28 Incorrect 2 ms 1388 KB Output isn't correct
29 Incorrect 4 ms 5204 KB Output isn't correct
30 Incorrect 4 ms 4180 KB Output isn't correct
31 Correct 3 ms 3028 KB Output is correct
32 Incorrect 4 ms 4052 KB Output isn't correct
33 Incorrect 5 ms 5204 KB Output isn't correct
34 Incorrect 2 ms 1620 KB Output isn't correct
35 Incorrect 3 ms 1876 KB Output isn't correct
36 Correct 7 ms 6612 KB Output is correct
37 Incorrect 0 ms 468 KB Output isn't correct
38 Correct 242 ms 55356 KB Output is correct
39 Incorrect 0 ms 468 KB Output isn't correct
40 Correct 26 ms 15476 KB Output is correct
41 Correct 0 ms 468 KB Output is correct
42 Correct 1 ms 1364 KB Output is correct
43 Correct 210 ms 51556 KB Output is correct
44 Correct 5 ms 5972 KB Output is correct
45 Incorrect 199 ms 52788 KB Output isn't correct
46 Correct 196 ms 55348 KB Output is correct
47 Incorrect 197 ms 52912 KB Output isn't correct
48 Correct 185 ms 55392 KB Output is correct
49 Correct 245 ms 55400 KB Output is correct
50 Correct 189 ms 55384 KB Output is correct
51 Correct 196 ms 55320 KB Output is correct
52 Correct 187 ms 55348 KB Output is correct
53 Correct 190 ms 54696 KB Output is correct
54 Correct 150 ms 42132 KB Output is correct
55 Incorrect 147 ms 40344 KB Output isn't correct
56 Correct 273 ms 55396 KB Output is correct
57 Incorrect 148 ms 35448 KB Output isn't correct
58 Correct 150 ms 40396 KB Output is correct
59 Correct 144 ms 37420 KB Output is correct
60 Correct 203 ms 47200 KB Output is correct
61 Correct 249 ms 55436 KB Output is correct
62 Correct 269 ms 55364 KB Output is correct
63 Correct 223 ms 55428 KB Output is correct
64 Correct 150 ms 38244 KB Output is correct
65 Correct 190 ms 54232 KB Output is correct
66 Correct 196 ms 51252 KB Output is correct
67 Correct 230 ms 55400 KB Output is correct
68 Correct 209 ms 55380 KB Output is correct
69 Correct 141 ms 35068 KB Output is correct
70 Incorrect 84 ms 15092 KB Output isn't correct
71 Incorrect 140 ms 28032 KB Output isn't correct
72 Incorrect 149 ms 33504 KB Output isn't correct
73 Correct 157 ms 33964 KB Output is correct
74 Incorrect 167 ms 35532 KB Output isn't correct
75 Incorrect 147 ms 37108 KB Output isn't correct
76 Incorrect 171 ms 38464 KB Output isn't correct
77 Incorrect 172 ms 38952 KB Output isn't correct
78 Incorrect 177 ms 39248 KB Output isn't correct
79 Incorrect 132 ms 11728 KB Output isn't correct
80 Incorrect 110 ms 13044 KB Output isn't correct
81 Incorrect 139 ms 13396 KB Output isn't correct
82 Incorrect 168 ms 41688 KB Output isn't correct
83 Incorrect 181 ms 41812 KB Output isn't correct
84 Incorrect 91 ms 7004 KB Output isn't correct
85 Incorrect 153 ms 40800 KB Output isn't correct
86 Incorrect 231 ms 54188 KB Output isn't correct
87 Incorrect 156 ms 39744 KB Output isn't correct
88 Correct 161 ms 40532 KB Output is correct
89 Correct 177 ms 49468 KB Output is correct
90 Incorrect 90 ms 29460 KB Output isn't correct
91 Incorrect 166 ms 44484 KB Output isn't correct
92 Incorrect 192 ms 46176 KB Output isn't correct
93 Incorrect 228 ms 53408 KB Output isn't correct
94 Correct 182 ms 47904 KB Output is correct
95 Incorrect 159 ms 41960 KB Output isn't correct
96 Correct 159 ms 41632 KB Output is correct
97 Incorrect 224 ms 54156 KB Output isn't correct
98 Incorrect 143 ms 41364 KB Output isn't correct
99 Incorrect 216 ms 47600 KB Output isn't correct
100 Incorrect 226 ms 52832 KB Output isn't correct