| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 833907 |
2023-08-22T09:27:34 Z |
vjudge1 |
Bomb (IZhO17_bomb) |
C++17 |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
