#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, b, a) for(int i = b - 1; i >= a; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;
typedef unsigned long long ull;
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 eng(seed);
ll random2(){
return (1ll << 31ll)*eng()+eng();
}
ll n,m,k,q,T;
const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod = 998244353;
const int MAXN = 2501;
bool grid[MAXN][MAXN] = {0};
bool covered[MAXN][MAXN] = {0};
int CS[MAXN][MAXN] = {0};
int sum(int i1, int j1, int i2, int j2){
return CS[i2+1][j2+1] - CS[i1][j2+1] - CS[i2+1][j1] + CS[i1][j1];
}
bool can_place(int i, int j, int a, int b){
if(n-i < a || m-j < b)return 0;
return (sum(i,j,i+a-1,j+b-1) == 0);
rep(c1,0,a){
rep(c2,0,b){
if(!grid[i+c1][j+c2])return 0;
}
}
return 1;
}
bool can_cover(int i, int j, int a, int b){
rep(dx,0,a){
rep(dy,0,b){
int i2 = i - dx;
int j2 = j - dy;
if(i2 >= 0 && j2 >= 0 && can_place(i2,j2,a,b))return 1;
}
}
return 0;
}
bool solve(int a, int b){
rep(c1,0,n){
rep(c2,0,m){
if(grid[c1][c2] && (c1 == n-1 || !grid[c1+1][c2] || c1 == 0 || !grid[c1-1][c2]) && !can_cover(c1,c2,a,b))return 0;
}
}
return 1;
}
int lft[MAXN][MAXN] = {0};
int up[MAXN][MAXN] = {0};
int mina = big;
int minb = big;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("fhc.txt","r",stdin);
// freopen("autput.txt","w",stdout);
ll a,b,c,d,e;
cin >> n >> m;
rep(c1,0,n){
string s;
cin >> s;
rep(c2,0,m){
grid[c1][c2] = (s[c2] == '1');
}
}
rep(c1,1,n+1){
rep(c2,1,m+1){
CS[c1][c2] = (!grid[c1-1][c2-1]) + CS[c1-1][c2] + CS[c1][c2-1] - CS[c1-1][c2-1];
}
}
rep(c1,0,n){
rep(c2,0,m){
if(grid[c1][c2]){
if(c1 == 0){
up[c1][c2] = 1;
}
else{
up[c1][c2] = up[c1-1][c2]+1;
}
if(c1 == n-1 || !grid[c1+1][c2])mina = min(mina, up[c1][c2]);
if(c2 == 0){
lft[c1][c2] = 1;
}
else{
lft[c1][c2] = lft[c1][c2-1]+1;
}
if(c2 == m-1 || !grid[c1][c2+1])minb = min(minb, lft[c1][c2]);
}
}
}
ll ans = 0;
rep(a,1,mina+1){
int lo = 1;
int hi = minb+1;
while(lo < hi-1){
int mid = (lo+hi)/2;
if(solve(a, mid)){
lo = mid;
}
else{
hi = mid;
}
}
ans = max(ans, ll(a)*ll(lo));
}
cout << ans << "\n";
return 0;
}
Compilation message
bomb.cpp: In function 'int main()':
bomb.cpp:88:8: warning: unused variable 'a' [-Wunused-variable]
88 | ll a,b,c,d,e;
| ^
bomb.cpp:88:10: warning: unused variable 'b' [-Wunused-variable]
88 | ll a,b,c,d,e;
| ^
bomb.cpp:88:12: warning: unused variable 'c' [-Wunused-variable]
88 | ll a,b,c,d,e;
| ^
bomb.cpp:88:14: warning: unused variable 'd' [-Wunused-variable]
88 | ll a,b,c,d,e;
| ^
bomb.cpp:88:16: warning: unused variable 'e' [-Wunused-variable]
88 | ll a,b,c,d,e;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
15 ms |
36436 KB |
Output is correct |
4 |
Correct |
15 ms |
36436 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
0 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
1236 KB |
Output is correct |
18 |
Correct |
1 ms |
1108 KB |
Output is correct |
19 |
Correct |
1 ms |
1364 KB |
Output is correct |
20 |
Correct |
1 ms |
1364 KB |
Output is correct |
21 |
Correct |
1 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
1108 KB |
Output is correct |
23 |
Correct |
3 ms |
1492 KB |
Output is correct |
24 |
Correct |
1 ms |
1236 KB |
Output is correct |
25 |
Correct |
2 ms |
1748 KB |
Output is correct |
26 |
Correct |
2 ms |
1876 KB |
Output is correct |
27 |
Correct |
3 ms |
5460 KB |
Output is correct |
28 |
Correct |
3 ms |
3028 KB |
Output is correct |
29 |
Correct |
441 ms |
7228 KB |
Output is correct |
30 |
Correct |
59 ms |
6612 KB |
Output is correct |
31 |
Correct |
104 ms |
4948 KB |
Output is correct |
32 |
Correct |
32 ms |
6312 KB |
Output is correct |
33 |
Correct |
108 ms |
7836 KB |
Output is correct |
34 |
Correct |
4 ms |
3412 KB |
Output is correct |
35 |
Correct |
10 ms |
4564 KB |
Output is correct |
36 |
Correct |
212 ms |
9228 KB |
Output is correct |
37 |
Correct |
1 ms |
596 KB |
Output is correct |
38 |
Execution timed out |
1099 ms |
79884 KB |
Time limit exceeded |
39 |
Correct |
1 ms |
596 KB |
Output is correct |
40 |
Execution timed out |
1090 ms |
22048 KB |
Time limit exceeded |
41 |
Correct |
1 ms |
596 KB |
Output is correct |
42 |
Correct |
14 ms |
1892 KB |
Output is correct |
43 |
Execution timed out |
1091 ms |
75956 KB |
Time limit exceeded |
44 |
Execution timed out |
1095 ms |
8532 KB |
Time limit exceeded |
45 |
Execution timed out |
1092 ms |
77388 KB |
Time limit exceeded |
46 |
Execution timed out |
1104 ms |
79820 KB |
Time limit exceeded |
47 |
Execution timed out |
1099 ms |
77328 KB |
Time limit exceeded |
48 |
Execution timed out |
1098 ms |
79832 KB |
Time limit exceeded |
49 |
Correct |
241 ms |
79784 KB |
Output is correct |
50 |
Execution timed out |
1103 ms |
79864 KB |
Time limit exceeded |
51 |
Execution timed out |
1095 ms |
79820 KB |
Time limit exceeded |
52 |
Execution timed out |
1076 ms |
79788 KB |
Time limit exceeded |
53 |
Execution timed out |
1105 ms |
79172 KB |
Time limit exceeded |
54 |
Execution timed out |
1103 ms |
66548 KB |
Time limit exceeded |
55 |
Execution timed out |
1090 ms |
64820 KB |
Time limit exceeded |
56 |
Execution timed out |
1096 ms |
79776 KB |
Time limit exceeded |
57 |
Execution timed out |
1093 ms |
59980 KB |
Time limit exceeded |
58 |
Execution timed out |
1078 ms |
64972 KB |
Time limit exceeded |
59 |
Execution timed out |
1064 ms |
61900 KB |
Time limit exceeded |
60 |
Execution timed out |
1077 ms |
71628 KB |
Time limit exceeded |
61 |
Execution timed out |
1088 ms |
79796 KB |
Time limit exceeded |
62 |
Execution timed out |
1094 ms |
79860 KB |
Time limit exceeded |
63 |
Execution timed out |
1095 ms |
79820 KB |
Time limit exceeded |
64 |
Execution timed out |
1081 ms |
62720 KB |
Time limit exceeded |
65 |
Execution timed out |
1096 ms |
78796 KB |
Time limit exceeded |
66 |
Execution timed out |
1090 ms |
75792 KB |
Time limit exceeded |
67 |
Execution timed out |
1097 ms |
79784 KB |
Time limit exceeded |
68 |
Execution timed out |
1091 ms |
79816 KB |
Time limit exceeded |
69 |
Execution timed out |
1098 ms |
59468 KB |
Time limit exceeded |
70 |
Execution timed out |
1094 ms |
34724 KB |
Time limit exceeded |
71 |
Execution timed out |
1095 ms |
52512 KB |
Time limit exceeded |
72 |
Execution timed out |
1067 ms |
58056 KB |
Time limit exceeded |
73 |
Execution timed out |
1087 ms |
58452 KB |
Time limit exceeded |
74 |
Execution timed out |
1092 ms |
60056 KB |
Time limit exceeded |
75 |
Execution timed out |
1096 ms |
61572 KB |
Time limit exceeded |
76 |
Execution timed out |
1094 ms |
62924 KB |
Time limit exceeded |
77 |
Execution timed out |
1093 ms |
63440 KB |
Time limit exceeded |
78 |
Execution timed out |
1097 ms |
63696 KB |
Time limit exceeded |
79 |
Execution timed out |
1095 ms |
36208 KB |
Time limit exceeded |
80 |
Execution timed out |
1088 ms |
37452 KB |
Time limit exceeded |
81 |
Execution timed out |
1097 ms |
37832 KB |
Time limit exceeded |
82 |
Execution timed out |
1092 ms |
66252 KB |
Time limit exceeded |
83 |
Execution timed out |
1096 ms |
66380 KB |
Time limit exceeded |
84 |
Correct |
138 ms |
31576 KB |
Output is correct |
85 |
Execution timed out |
1095 ms |
65236 KB |
Time limit exceeded |
86 |
Correct |
195 ms |
78744 KB |
Output is correct |
87 |
Execution timed out |
1100 ms |
64156 KB |
Time limit exceeded |
88 |
Execution timed out |
1086 ms |
65100 KB |
Time limit exceeded |
89 |
Execution timed out |
1091 ms |
73860 KB |
Time limit exceeded |
90 |
Execution timed out |
1093 ms |
49012 KB |
Time limit exceeded |
91 |
Execution timed out |
1092 ms |
68956 KB |
Time limit exceeded |
92 |
Execution timed out |
1094 ms |
70588 KB |
Time limit exceeded |
93 |
Correct |
518 ms |
77884 KB |
Output is correct |
94 |
Execution timed out |
1082 ms |
72516 KB |
Time limit exceeded |
95 |
Execution timed out |
1097 ms |
66468 KB |
Time limit exceeded |
96 |
Execution timed out |
1100 ms |
66060 KB |
Time limit exceeded |
97 |
Correct |
514 ms |
78540 KB |
Output is correct |
98 |
Execution timed out |
1092 ms |
65868 KB |
Time limit exceeded |
99 |
Execution timed out |
1096 ms |
72096 KB |
Time limit exceeded |
100 |
Correct |
272 ms |
77308 KB |
Output is correct |