# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
505722 |
2022-01-11T07:13:59 Z |
pragmatist |
Bomb (IZhO17_bomb) |
C++17 |
|
1000 ms |
104408 KB |
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define x first
#define y second
#define int long long
#define nl "\n"
using namespace std;
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair <ll, ll> pii;
const int N = (int)1e6 + 7;
const int M = (int)5e6 + 7;
const ll MOD = (ll)1e9 + 7;
const int inf = (int)1e9 + 7;
const ll INF = (ll)3e18 + 7;
pii dir[] = {{-1, -1}, {1, 1}, {-1, 1}, {1, -1}};
int n, m;
char c[2501][2501];
int used[2501][2501], w[2501][2501];
int get(int x1, int y1, int x2, int y2) {
return w[x2][y2] - w[x2][y1-1] - w[x1-1][y2] + w[x1-1][y1-1];
}
void upd(int x1, int y1, int x2, int y2) {
used[x1][y1]++;
used[x1][y2+1]--;
used[x2+1][y1]--;
used[x2+1][y2+1]++;
}
void solve() {
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin >> c[i][j];
w[i][j] = w[i-1][j] + w[i][j-1] - w[i-1][j-1] + (c[i][j] == '1');
}
}
int ans = inf;
if(n == 1) {
int cur = 0;
for(int i = 1; i <= m; ++i) {
if(c[1][i] == '1') cur++;
else {
if(cur > 0) ans = min(ans, cur);
cur = 0;
}
}
if(c[1][m] == '1') ans = min(ans, cur);
cout << ans << nl;
return;
}
if(m == 1) {
int cur = 0;
for(int i = 1; i <= n; ++i) {
if(c[i][1] == '1') cur++;
else {
if(cur > 0) ans = min(ans, cur);
cur = 0;
}
}
if(c[n][1] == '1') ans = min(ans, cur);
cout << ans << nl;
return;
}
ans = 0;
for(int e = 1; e <= n; ++e) {
for(int f = 1; f <= n; ++f) {
bool ok = 1;
for(int i = 1; i <= n; ++i) fill(used[i] + 1, used[i] + 1 + m, 0);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(i + e - 1 > n || j + f - 1 > m) break;
int x = get(i, j, i + e - 1, j + f - 1);
if(x == e * f) {
upd(i, j, i + e - 1, j + f - 1);
}
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
used[i][j] += used[i-1][j] + used[i][j-1] - used[i-1][j-1];
}
}
for(int i = 1; i <= n && ok; ++i) {
for(int j = 1; j <= m && ok; ++j) {
if(c[i][j] == '1') ok &= (used[i][j] > 0);
}
}
if(ok) {
ans = max(ans, e * f);
//cout << e << ' ' << f << nl;
}
}
}
cout << ans << nl;
}
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
cout.tie(0);
int test = 1;
//cin >> test;
for(int i = 1; i <= test; ++i) {
//cout << "Case " << i << ": ";
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
11 ms |
16460 KB |
Output is correct |
4 |
Correct |
9 ms |
16460 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
13 |
Correct |
1 ms |
460 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
460 KB |
Output is correct |
17 |
Correct |
63 ms |
1076 KB |
Output is correct |
18 |
Correct |
72 ms |
1128 KB |
Output is correct |
19 |
Correct |
209 ms |
1408 KB |
Output is correct |
20 |
Correct |
214 ms |
1356 KB |
Output is correct |
21 |
Correct |
53 ms |
976 KB |
Output is correct |
22 |
Correct |
149 ms |
1228 KB |
Output is correct |
23 |
Correct |
370 ms |
1520 KB |
Output is correct |
24 |
Correct |
131 ms |
1256 KB |
Output is correct |
25 |
Correct |
342 ms |
1524 KB |
Output is correct |
26 |
Correct |
417 ms |
1528 KB |
Output is correct |
27 |
Execution timed out |
1084 ms |
4556 KB |
Time limit exceeded |
28 |
Execution timed out |
1088 ms |
5068 KB |
Time limit exceeded |
29 |
Execution timed out |
1084 ms |
6348 KB |
Time limit exceeded |
30 |
Execution timed out |
1100 ms |
7756 KB |
Time limit exceeded |
31 |
Execution timed out |
1088 ms |
6092 KB |
Time limit exceeded |
32 |
Execution timed out |
1090 ms |
6988 KB |
Time limit exceeded |
33 |
Execution timed out |
1064 ms |
8140 KB |
Time limit exceeded |
34 |
Execution timed out |
1080 ms |
5324 KB |
Time limit exceeded |
35 |
Execution timed out |
1091 ms |
8140 KB |
Time limit exceeded |
36 |
Execution timed out |
1091 ms |
8140 KB |
Time limit exceeded |
37 |
Correct |
1 ms |
460 KB |
Output is correct |
38 |
Execution timed out |
1074 ms |
104240 KB |
Time limit exceeded |
39 |
Correct |
1 ms |
460 KB |
Output is correct |
40 |
Execution timed out |
1100 ms |
21552 KB |
Time limit exceeded |
41 |
Correct |
1 ms |
460 KB |
Output is correct |
42 |
Correct |
375 ms |
1528 KB |
Output is correct |
43 |
Execution timed out |
1091 ms |
104288 KB |
Time limit exceeded |
44 |
Execution timed out |
1099 ms |
8140 KB |
Time limit exceeded |
45 |
Execution timed out |
1098 ms |
104268 KB |
Time limit exceeded |
46 |
Execution timed out |
1103 ms |
104260 KB |
Time limit exceeded |
47 |
Execution timed out |
1092 ms |
104260 KB |
Time limit exceeded |
48 |
Execution timed out |
1103 ms |
104180 KB |
Time limit exceeded |
49 |
Execution timed out |
1088 ms |
104288 KB |
Time limit exceeded |
50 |
Execution timed out |
1089 ms |
104200 KB |
Time limit exceeded |
51 |
Execution timed out |
1090 ms |
104392 KB |
Time limit exceeded |
52 |
Execution timed out |
1096 ms |
104300 KB |
Time limit exceeded |
53 |
Execution timed out |
1095 ms |
104216 KB |
Time limit exceeded |
54 |
Execution timed out |
1090 ms |
104224 KB |
Time limit exceeded |
55 |
Execution timed out |
1104 ms |
104280 KB |
Time limit exceeded |
56 |
Execution timed out |
1097 ms |
104296 KB |
Time limit exceeded |
57 |
Execution timed out |
1082 ms |
104288 KB |
Time limit exceeded |
58 |
Execution timed out |
1083 ms |
104292 KB |
Time limit exceeded |
59 |
Execution timed out |
1100 ms |
104256 KB |
Time limit exceeded |
60 |
Execution timed out |
1099 ms |
104240 KB |
Time limit exceeded |
61 |
Execution timed out |
1100 ms |
104296 KB |
Time limit exceeded |
62 |
Execution timed out |
1101 ms |
104200 KB |
Time limit exceeded |
63 |
Execution timed out |
1092 ms |
104272 KB |
Time limit exceeded |
64 |
Execution timed out |
1106 ms |
104232 KB |
Time limit exceeded |
65 |
Execution timed out |
1106 ms |
104188 KB |
Time limit exceeded |
66 |
Execution timed out |
1064 ms |
104284 KB |
Time limit exceeded |
67 |
Execution timed out |
1100 ms |
104264 KB |
Time limit exceeded |
68 |
Execution timed out |
1093 ms |
104212 KB |
Time limit exceeded |
69 |
Execution timed out |
1101 ms |
104184 KB |
Time limit exceeded |
70 |
Execution timed out |
1104 ms |
83400 KB |
Time limit exceeded |
71 |
Execution timed out |
1102 ms |
104212 KB |
Time limit exceeded |
72 |
Execution timed out |
1097 ms |
104304 KB |
Time limit exceeded |
73 |
Execution timed out |
1104 ms |
104280 KB |
Time limit exceeded |
74 |
Execution timed out |
1101 ms |
104240 KB |
Time limit exceeded |
75 |
Execution timed out |
1068 ms |
104260 KB |
Time limit exceeded |
76 |
Execution timed out |
1086 ms |
104260 KB |
Time limit exceeded |
77 |
Execution timed out |
1094 ms |
104296 KB |
Time limit exceeded |
78 |
Execution timed out |
1103 ms |
104212 KB |
Time limit exceeded |
79 |
Execution timed out |
1089 ms |
104312 KB |
Time limit exceeded |
80 |
Execution timed out |
1092 ms |
104260 KB |
Time limit exceeded |
81 |
Execution timed out |
1096 ms |
104192 KB |
Time limit exceeded |
82 |
Execution timed out |
1095 ms |
104288 KB |
Time limit exceeded |
83 |
Execution timed out |
1095 ms |
104276 KB |
Time limit exceeded |
84 |
Execution timed out |
1078 ms |
104276 KB |
Time limit exceeded |
85 |
Execution timed out |
1100 ms |
104196 KB |
Time limit exceeded |
86 |
Execution timed out |
1100 ms |
104240 KB |
Time limit exceeded |
87 |
Execution timed out |
1099 ms |
104276 KB |
Time limit exceeded |
88 |
Execution timed out |
1073 ms |
104244 KB |
Time limit exceeded |
89 |
Execution timed out |
1091 ms |
104300 KB |
Time limit exceeded |
90 |
Execution timed out |
1084 ms |
83400 KB |
Time limit exceeded |
91 |
Execution timed out |
1101 ms |
104264 KB |
Time limit exceeded |
92 |
Execution timed out |
1092 ms |
104236 KB |
Time limit exceeded |
93 |
Execution timed out |
1096 ms |
104260 KB |
Time limit exceeded |
94 |
Execution timed out |
1103 ms |
104260 KB |
Time limit exceeded |
95 |
Execution timed out |
1095 ms |
104180 KB |
Time limit exceeded |
96 |
Execution timed out |
1105 ms |
104260 KB |
Time limit exceeded |
97 |
Execution timed out |
1097 ms |
104204 KB |
Time limit exceeded |
98 |
Execution timed out |
1100 ms |
104216 KB |
Time limit exceeded |
99 |
Execution timed out |
1095 ms |
104408 KB |
Time limit exceeded |
100 |
Execution timed out |
1098 ms |
104216 KB |
Time limit exceeded |