// Online C++ compiler to run C++ program online
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[2505];
int v[2505][2505],a[2505][2505];
bool was[2505][2505];
int queryA(int x1,int y1,int x2,int y2){
return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}
int queryV(int x1,int y1,int x2,int y2){
return v[x2][y2]-v[x1-1][y2]-v[x2][y1-1]+v[x1-1][y1-1];
}
bool check(int x,int y){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
v[i][j]=0;
}
}
for(int i=1;i+x<=n+1;i++){
for(int j=1;j+y<=m+1;j++){
if(queryA(i,j,i+x-1,j+y-1)==x*y){
v[i][j]=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]+=v[i][j-1];
v[i][j]-=v[i-1][j-1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(queryA(i,j,i,j)==1&&queryV(max(1,i-x+1),max(1,j-y+1),i,j)==0){
return false;
}
}
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++){
a[i][j]=(int)(s[j]-'0');
a[i][j]+=a[i-1][j];
a[i][j]+=a[i][j-1];
a[i][j]-=a[i-1][j-1];
}
}
int lx=n;
int ly=m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(queryA(i,j,i,j)==0) continue;
int ptr=j;
while(ptr+1<=m&&queryA(i,ptr+1,i,ptr+1)==1) ptr++;
ly=min(ly,ptr-j+1);
j=ptr;
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(queryA(i,j,i,j)==0) continue;
int ptr=i;
while(ptr+1<=n&&queryA(ptr+1,j,ptr+1,j)==1) ptr++;
lx=min(lx,ptr-i+1);
i=ptr;
}
}
int ans=0;
for(int x=lx;x>=1;x--){
int l=1,r=ly;
while(l<=r){
int mid=(l+r)/2;
if(check(x,mid)) ans=max(ans,x*mid),l=mid+1; else r=mid-1;
}
}
printf("%d\n",ans);
return 0;
}
Compilation message
bomb.cpp: In function 'int main()':
bomb.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
bomb.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%s",s+1);
| ~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
9 ms |
50264 KB |
Output is correct |
4 |
Correct |
10 ms |
50264 KB |
Output is correct |
5 |
Correct |
1 ms |
4440 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4440 KB |
Output is correct |
8 |
Correct |
1 ms |
4696 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4440 KB |
Output is correct |
13 |
Correct |
1 ms |
4440 KB |
Output is correct |
14 |
Correct |
1 ms |
4440 KB |
Output is correct |
15 |
Correct |
1 ms |
4440 KB |
Output is correct |
16 |
Correct |
1 ms |
4440 KB |
Output is correct |
17 |
Correct |
2 ms |
8540 KB |
Output is correct |
18 |
Correct |
2 ms |
8536 KB |
Output is correct |
19 |
Correct |
5 ms |
8536 KB |
Output is correct |
20 |
Correct |
4 ms |
8540 KB |
Output is correct |
21 |
Correct |
2 ms |
8536 KB |
Output is correct |
22 |
Correct |
2 ms |
8536 KB |
Output is correct |
23 |
Correct |
6 ms |
8536 KB |
Output is correct |
24 |
Correct |
5 ms |
8536 KB |
Output is correct |
25 |
Correct |
8 ms |
8540 KB |
Output is correct |
26 |
Correct |
5 ms |
8536 KB |
Output is correct |
27 |
Correct |
4 ms |
12632 KB |
Output is correct |
28 |
Correct |
14 ms |
12632 KB |
Output is correct |
29 |
Correct |
390 ms |
12888 KB |
Output is correct |
30 |
Correct |
561 ms |
12732 KB |
Output is correct |
31 |
Correct |
328 ms |
12732 KB |
Output is correct |
32 |
Correct |
414 ms |
12732 KB |
Output is correct |
33 |
Correct |
825 ms |
16976 KB |
Output is correct |
34 |
Correct |
14 ms |
12632 KB |
Output is correct |
35 |
Correct |
113 ms |
16836 KB |
Output is correct |
36 |
Correct |
373 ms |
16832 KB |
Output is correct |
37 |
Correct |
1 ms |
4440 KB |
Output is correct |
38 |
Execution timed out |
1018 ms |
55120 KB |
Time limit exceeded |
39 |
Correct |
1 ms |
4440 KB |
Output is correct |
40 |
Execution timed out |
1050 ms |
24920 KB |
Time limit exceeded |
41 |
Correct |
1 ms |
4440 KB |
Output is correct |
42 |
Correct |
15 ms |
8536 KB |
Output is correct |
43 |
Execution timed out |
1024 ms |
55120 KB |
Time limit exceeded |
44 |
Execution timed out |
1031 ms |
16728 KB |
Time limit exceeded |
45 |
Execution timed out |
1018 ms |
55136 KB |
Time limit exceeded |
46 |
Execution timed out |
1096 ms |
55124 KB |
Time limit exceeded |
47 |
Execution timed out |
1006 ms |
55244 KB |
Time limit exceeded |
48 |
Execution timed out |
1027 ms |
55128 KB |
Time limit exceeded |
49 |
Execution timed out |
1008 ms |
55312 KB |
Time limit exceeded |
50 |
Execution timed out |
1028 ms |
55124 KB |
Time limit exceeded |
51 |
Execution timed out |
1033 ms |
55120 KB |
Time limit exceeded |
52 |
Execution timed out |
1033 ms |
55252 KB |
Time limit exceeded |
53 |
Execution timed out |
1006 ms |
55120 KB |
Time limit exceeded |
54 |
Execution timed out |
1033 ms |
55116 KB |
Time limit exceeded |
55 |
Execution timed out |
1016 ms |
55420 KB |
Time limit exceeded |
56 |
Execution timed out |
1012 ms |
55120 KB |
Time limit exceeded |
57 |
Execution timed out |
1045 ms |
55120 KB |
Time limit exceeded |
58 |
Execution timed out |
1032 ms |
55244 KB |
Time limit exceeded |
59 |
Execution timed out |
1040 ms |
55120 KB |
Time limit exceeded |
60 |
Execution timed out |
1039 ms |
55120 KB |
Time limit exceeded |
61 |
Execution timed out |
1020 ms |
55120 KB |
Time limit exceeded |
62 |
Execution timed out |
1036 ms |
55124 KB |
Time limit exceeded |
63 |
Execution timed out |
1036 ms |
55252 KB |
Time limit exceeded |
64 |
Execution timed out |
1032 ms |
55240 KB |
Time limit exceeded |
65 |
Execution timed out |
1043 ms |
55116 KB |
Time limit exceeded |
66 |
Execution timed out |
1006 ms |
55116 KB |
Time limit exceeded |
67 |
Execution timed out |
1012 ms |
55248 KB |
Time limit exceeded |
68 |
Execution timed out |
1035 ms |
55120 KB |
Time limit exceeded |
69 |
Execution timed out |
1044 ms |
55120 KB |
Time limit exceeded |
70 |
Execution timed out |
1043 ms |
47696 KB |
Time limit exceeded |
71 |
Execution timed out |
1020 ms |
55124 KB |
Time limit exceeded |
72 |
Execution timed out |
1041 ms |
55120 KB |
Time limit exceeded |
73 |
Execution timed out |
1029 ms |
55120 KB |
Time limit exceeded |
74 |
Execution timed out |
1025 ms |
55116 KB |
Time limit exceeded |
75 |
Execution timed out |
1038 ms |
55228 KB |
Time limit exceeded |
76 |
Execution timed out |
1034 ms |
55120 KB |
Time limit exceeded |
77 |
Execution timed out |
1022 ms |
55120 KB |
Time limit exceeded |
78 |
Execution timed out |
1032 ms |
55256 KB |
Time limit exceeded |
79 |
Execution timed out |
1040 ms |
55144 KB |
Time limit exceeded |
80 |
Execution timed out |
1054 ms |
55120 KB |
Time limit exceeded |
81 |
Execution timed out |
1043 ms |
55120 KB |
Time limit exceeded |
82 |
Execution timed out |
1004 ms |
55120 KB |
Time limit exceeded |
83 |
Execution timed out |
1012 ms |
55120 KB |
Time limit exceeded |
84 |
Execution timed out |
1051 ms |
55120 KB |
Time limit exceeded |
85 |
Execution timed out |
1043 ms |
55120 KB |
Time limit exceeded |
86 |
Execution timed out |
1016 ms |
55120 KB |
Time limit exceeded |
87 |
Execution timed out |
1014 ms |
55120 KB |
Time limit exceeded |
88 |
Execution timed out |
1016 ms |
55124 KB |
Time limit exceeded |
89 |
Execution timed out |
1045 ms |
55124 KB |
Time limit exceeded |
90 |
Execution timed out |
1040 ms |
47696 KB |
Time limit exceeded |
91 |
Execution timed out |
1029 ms |
55120 KB |
Time limit exceeded |
92 |
Execution timed out |
1030 ms |
55120 KB |
Time limit exceeded |
93 |
Execution timed out |
1018 ms |
55120 KB |
Time limit exceeded |
94 |
Execution timed out |
1018 ms |
55112 KB |
Time limit exceeded |
95 |
Execution timed out |
1035 ms |
55120 KB |
Time limit exceeded |
96 |
Execution timed out |
1050 ms |
55120 KB |
Time limit exceeded |
97 |
Execution timed out |
1024 ms |
55120 KB |
Time limit exceeded |
98 |
Execution timed out |
1010 ms |
55116 KB |
Time limit exceeded |
99 |
Execution timed out |
1028 ms |
56400 KB |
Time limit exceeded |
100 |
Execution timed out |
1035 ms |
56400 KB |
Time limit exceeded |