#include <bits/stdc++.h>
#define DIM 2502
using namespace std;
int n,m,i,j;
char s[DIM];
int dp_up[DIM][DIM],St[DIM],Dr[DIM],v[DIM][DIM],a[DIM][DIM];
deque <int> d;
struct event{
int x,y,x2,y2,val;
};
vector <event> events;
inline int cmp (event a, event b){
return a.val < b.val;
}
int verif (int poz){
memset (v,0,sizeof v);
int ok = 0;
for (int i=poz;i<events.size();i++){
int x = events[i].x, x2 = events[i].x2, y = events[i].y, y2 = events[i].y2;
if (x <= 3 && 3 <= x2 && y <= 6 && 6 <= y2)
ok = 1;
v[x][y]++;
v[x][y2+1]--;
v[x2+1][y]--;
v[x2+1][y2+1]++;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1];
if (!v[i][j] && a[i][j])
return 0;
}
return 1;
}
int main (){
//ifstream cin ("bomb.in");
//ofstream cout ("bomb.out");
cin>>n>>m;
for (i=1;i<=n;i++){
cin>>s+1;
for (j=1;j<=m;j++)
a[i][j] = s[j] - '0';
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (a[i][j])
dp_up[i][j] = 1 + dp_up[i-1][j];
for (i=1;i<=n;i++){
memset (St,0,sizeof St);
memset (Dr,0,sizeof Dr);
d.clear();
int last = 0;
for (j=1;j<=m;j++){
if (!dp_up[i][j]){
d.clear();
last = j;
}
while (!d.empty() && dp_up[i][j] <= dp_up[i][d.back()])
d.pop_back();
if (d.empty())
St[j] = last;
else St[j] = d.back();
d.push_back(j);
}
d.clear(), last = m+1;
for (j=m;j;j--){
if (!dp_up[i][j]){
d.clear();
last = j;
}
while (!d.empty() && dp_up[i][j] <= dp_up[i][d.back()])
d.pop_back();
if (d.empty())
Dr[j] = last;
else Dr[j] = d.back();
d.push_back(j);
}
for (j=1;j<=m;j++){
if (!dp_up[i][j])
continue;
int x = i - dp_up[i][j] + 1, x2 = i;
int y = St[j] + 1, y2 = Dr[j] - 1;
if (x == 1 && x2 == 3 && y == 1 && y2 == 6)
x = 1;
events.push_back({x,y,x2,y2,dp_up[i][j] * (Dr[j] - St[j] - 1)});
}
}
sort (events.begin(),events.end(),cmp);
int st = 0, dr = events.size()-1, sol = 0;
while (st <= dr){
int mid = (st+dr)>>1;
if (verif(mid)){
sol = events[mid].val;
st = mid+1;
} else dr = mid-1;
}
cout<<sol;
return 0;
}
Compilation message
bomb.cpp: In function 'int verif(int)':
bomb.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i=poz;i<events.size();i++){
| ~^~~~~~~~~~~~~~
bomb.cpp:22:9: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
22 | int ok = 0;
| ^~
bomb.cpp: In function 'int main()':
bomb.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | cin>>s+1;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
24812 KB |
Output is correct |
2 |
Correct |
20 ms |
24940 KB |
Output is correct |
3 |
Correct |
60 ms |
45036 KB |
Output is correct |
4 |
Correct |
59 ms |
45100 KB |
Output is correct |
5 |
Correct |
49 ms |
25088 KB |
Output is correct |
6 |
Correct |
43 ms |
24940 KB |
Output is correct |
7 |
Incorrect |
26 ms |
24960 KB |
Output isn't correct |
8 |
Incorrect |
30 ms |
24960 KB |
Output isn't correct |
9 |
Incorrect |
33 ms |
24940 KB |
Output isn't correct |
10 |
Incorrect |
30 ms |
24940 KB |
Output isn't correct |
11 |
Incorrect |
30 ms |
25068 KB |
Output isn't correct |
12 |
Incorrect |
26 ms |
24940 KB |
Output isn't correct |
13 |
Incorrect |
30 ms |
24960 KB |
Output isn't correct |
14 |
Correct |
33 ms |
24940 KB |
Output is correct |
15 |
Incorrect |
33 ms |
24940 KB |
Output isn't correct |
16 |
Incorrect |
36 ms |
25196 KB |
Output isn't correct |
17 |
Correct |
46 ms |
25452 KB |
Output is correct |
18 |
Incorrect |
34 ms |
25324 KB |
Output isn't correct |
19 |
Incorrect |
44 ms |
25580 KB |
Output isn't correct |
20 |
Incorrect |
44 ms |
25600 KB |
Output isn't correct |
21 |
Incorrect |
33 ms |
25196 KB |
Output isn't correct |
22 |
Incorrect |
38 ms |
25452 KB |
Output isn't correct |
23 |
Incorrect |
46 ms |
25708 KB |
Output isn't correct |
24 |
Incorrect |
43 ms |
25472 KB |
Output isn't correct |
25 |
Incorrect |
50 ms |
25836 KB |
Output isn't correct |
26 |
Incorrect |
57 ms |
26024 KB |
Output isn't correct |
27 |
Incorrect |
89 ms |
29672 KB |
Output isn't correct |
28 |
Incorrect |
47 ms |
26732 KB |
Output isn't correct |
29 |
Incorrect |
100 ms |
30940 KB |
Output isn't correct |
30 |
Incorrect |
86 ms |
29792 KB |
Output isn't correct |
31 |
Incorrect |
71 ms |
28516 KB |
Output isn't correct |
32 |
Incorrect |
75 ms |
29156 KB |
Output isn't correct |
33 |
Incorrect |
91 ms |
30816 KB |
Output isn't correct |
34 |
Incorrect |
50 ms |
26988 KB |
Output isn't correct |
35 |
Incorrect |
68 ms |
28220 KB |
Output isn't correct |
36 |
Incorrect |
125 ms |
34516 KB |
Output isn't correct |
37 |
Correct |
36 ms |
25196 KB |
Output is correct |
38 |
Runtime error |
293 ms |
131076 KB |
Execution killed with signal 9 |
39 |
Correct |
36 ms |
25068 KB |
Output is correct |
40 |
Incorrect |
284 ms |
53932 KB |
Output isn't correct |
41 |
Correct |
36 ms |
25068 KB |
Output is correct |
42 |
Correct |
51 ms |
25932 KB |
Output is correct |
43 |
Runtime error |
441 ms |
131076 KB |
Execution killed with signal 9 |
44 |
Correct |
114 ms |
32496 KB |
Output is correct |
45 |
Execution timed out |
1063 ms |
131076 KB |
Time limit exceeded |
46 |
Runtime error |
335 ms |
131076 KB |
Execution killed with signal 9 |
47 |
Execution timed out |
1099 ms |
131072 KB |
Time limit exceeded |
48 |
Runtime error |
324 ms |
131076 KB |
Execution killed with signal 9 |
49 |
Runtime error |
297 ms |
131076 KB |
Execution killed with signal 9 |
50 |
Runtime error |
320 ms |
131076 KB |
Execution killed with signal 9 |
51 |
Runtime error |
322 ms |
131076 KB |
Execution killed with signal 9 |
52 |
Runtime error |
320 ms |
131076 KB |
Execution killed with signal 9 |
53 |
Runtime error |
324 ms |
131076 KB |
Execution killed with signal 9 |
54 |
Incorrect |
990 ms |
110740 KB |
Output isn't correct |
55 |
Execution timed out |
1097 ms |
107904 KB |
Time limit exceeded |
56 |
Runtime error |
300 ms |
131076 KB |
Execution killed with signal 9 |
57 |
Execution timed out |
1102 ms |
103040 KB |
Time limit exceeded |
58 |
Execution timed out |
1087 ms |
107904 KB |
Time limit exceeded |
59 |
Execution timed out |
1079 ms |
104492 KB |
Time limit exceeded |
60 |
Runtime error |
860 ms |
131076 KB |
Execution killed with signal 9 |
61 |
Runtime error |
291 ms |
131076 KB |
Execution killed with signal 9 |
62 |
Runtime error |
290 ms |
131076 KB |
Execution killed with signal 9 |
63 |
Runtime error |
290 ms |
131076 KB |
Execution killed with signal 9 |
64 |
Incorrect |
937 ms |
105768 KB |
Output isn't correct |
65 |
Runtime error |
833 ms |
131076 KB |
Execution killed with signal 9 |
66 |
Runtime error |
846 ms |
131076 KB |
Execution killed with signal 9 |
67 |
Runtime error |
314 ms |
131076 KB |
Execution killed with signal 9 |
68 |
Runtime error |
318 ms |
131076 KB |
Execution killed with signal 9 |
69 |
Execution timed out |
1104 ms |
103424 KB |
Time limit exceeded |
70 |
Incorrect |
475 ms |
61764 KB |
Output isn't correct |
71 |
Incorrect |
761 ms |
86188 KB |
Output isn't correct |
72 |
Incorrect |
968 ms |
99968 KB |
Output isn't correct |
73 |
Execution timed out |
1076 ms |
103808 KB |
Time limit exceeded |
74 |
Execution timed out |
1066 ms |
102400 KB |
Time limit exceeded |
75 |
Execution timed out |
1099 ms |
105344 KB |
Time limit exceeded |
76 |
Execution timed out |
1101 ms |
108032 KB |
Time limit exceeded |
77 |
Execution timed out |
1062 ms |
110080 KB |
Time limit exceeded |
78 |
Execution timed out |
1074 ms |
109312 KB |
Time limit exceeded |
79 |
Incorrect |
537 ms |
58596 KB |
Output isn't correct |
80 |
Incorrect |
494 ms |
59236 KB |
Output isn't correct |
81 |
Incorrect |
648 ms |
63224 KB |
Output isn't correct |
82 |
Execution timed out |
1036 ms |
113640 KB |
Time limit exceeded |
83 |
Execution timed out |
1100 ms |
113408 KB |
Time limit exceeded |
84 |
Incorrect |
416 ms |
56232 KB |
Output isn't correct |
85 |
Execution timed out |
1084 ms |
108672 KB |
Time limit exceeded |
86 |
Runtime error |
378 ms |
131076 KB |
Execution killed with signal 9 |
87 |
Execution timed out |
1062 ms |
105452 KB |
Time limit exceeded |
88 |
Execution timed out |
1073 ms |
112640 KB |
Time limit exceeded |
89 |
Execution timed out |
1057 ms |
131072 KB |
Time limit exceeded |
90 |
Incorrect |
612 ms |
81068 KB |
Output isn't correct |
91 |
Execution timed out |
1065 ms |
131072 KB |
Time limit exceeded |
92 |
Execution timed out |
1100 ms |
131072 KB |
Time limit exceeded |
93 |
Runtime error |
377 ms |
131076 KB |
Execution killed with signal 9 |
94 |
Execution timed out |
1103 ms |
131072 KB |
Time limit exceeded |
95 |
Execution timed out |
1097 ms |
113688 KB |
Time limit exceeded |
96 |
Execution timed out |
1105 ms |
113480 KB |
Time limit exceeded |
97 |
Runtime error |
377 ms |
131076 KB |
Execution killed with signal 9 |
98 |
Execution timed out |
1107 ms |
113408 KB |
Time limit exceeded |
99 |
Execution timed out |
1060 ms |
131072 KB |
Time limit exceeded |
100 |
Runtime error |
382 ms |
131076 KB |
Execution killed with signal 9 |