oj.uz

Submission #1106819

# Submission time Handle Problem Language Result Execution time Memory
1106819 2024-10-31T05:47:37 Z stdfloat Bomb (IZhO17_bomb) C++17
8 / 100
 1000 ms 16032 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	vector<string> a(n);
	for (auto &i : a)
		cin >> i;

	int mn1 = n, mn2 = m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == '0') continue;

			if (1 < (!i || a[i - 1][j] == '0') + (!j || a[i][j - 1] == '0') + (i + 1 == n || a[i + 1][j] == '0') + (j + 1 == m || a[i][j + 1] == '0')) {
				int l = i, r = i;
				while (0 < l && a[l - 1][j] == '1') l--;
				while (r + 1 < n && a[r + 1][j] == '1') r++;
				mn1 = min(mn1, max(r - i, i - l) + 1);
				
				l = r = j;
				while (0 < l && a[i][l - 1] == '1') l--;
				while (r + 1 < m && a[i][r + 1] == '1') r++;
				mn2 = min(mn2, max(r - j, j - l) + 1);
			}
		}
	}

	bool ok = true;
	vector<vector<bool>> vis(n, vector<bool>(m));
	for (int i = 0; i + mn1 <= n; i++) {
		for (int j = 0; j + mn2 <= m; j++) {
			if (a[i][j] == '0') continue;

			bool tr = true;
			for (int k = i; k < i + mn1 && tr; k++) {
				for (int l = j; l < j + mn2 && tr; l++)
					tr = (a[k][l] == '1');
			}

			ok = vis[i][j];
			if (!tr) continue;

			for (int k = i; k < i + mn1; k++) {
				for (int l = j; l < j + mn2; l++)
					vis[k][l] = true;
			}

			ok = true;
		}
	}

	for (int i = 0; i < n && ok; i++) {
		for (int j = 0; j < m && ok; j++)
			ok = (a[i][j] == '0' || vis[i][j]);
	}

	assert(ok);

	cout << mn1 * mn2;
}

Subtask #1
8.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 3 ms 592 KB Output isn't correct
4 Incorrect 2 ms 592 KB Output isn't correct
5 Incorrect 1 ms 336 KB Output isn't correct
6 Incorrect 1 ms 500 KB Output isn't correct
7 Runtime error 1 ms 592 KB Execution killed with signal 6
8 Runtime error 1 ms 592 KB Execution killed with signal 6
9 Runtime error 1 ms 760 KB Execution killed with signal 6
10 Runtime error 1 ms 592 KB Execution killed with signal 6
11 Runtime error 1 ms 592 KB Execution killed with signal 6
12 Runtime error 1 ms 592 KB Execution killed with signal 6
13 Correct 1 ms 336 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Runtime error 1 ms 592 KB Execution killed with signal 6
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Runtime error 1 ms 592 KB Execution killed with signal 6
19 Runtime error 2 ms 592 KB Execution killed with signal 6
20 Runtime error 2 ms 592 KB Execution killed with signal 6
21 Runtime error 1 ms 592 KB Execution killed with signal 6
22 Runtime error 2 ms 592 KB Execution killed with signal 6
23 Runtime error 1 ms 760 KB Execution killed with signal 6
24 Runtime error 1 ms 592 KB Execution killed with signal 6
25 Runtime error 1 ms 592 KB Execution killed with signal 6
26 Runtime error 1 ms 592 KB Execution killed with signal 6
27 Runtime error 2 ms 1016 KB Execution killed with signal 6
28 Runtime error 2 ms 848 KB Execution killed with signal 6
29 Runtime error 529 ms 876 KB Execution killed with signal 6
30 Runtime error 5 ms 1104 KB Execution killed with signal 6
31 Runtime error 5 ms 848 KB Execution killed with signal 6
32 Runtime error 3 ms 860 KB Execution killed with signal 6
33 Runtime error 7 ms 1048 KB Execution killed with signal 6
34 Runtime error 2 ms 848 KB Execution killed with signal 6
35 Runtime error 2 ms 1104 KB Execution killed with signal 6
36 Runtime error 3 ms 1104 KB Execution killed with signal 6
37 Runtime error 1 ms 592 KB Execution killed with signal 6
38 Correct 39 ms 8184 KB Output is correct
39 Runtime error 1 ms 592 KB Execution killed with signal 6
40 Execution timed out 1086 ms 1360 KB Time limit exceeded
41 Runtime error 1 ms 592 KB Execution killed with signal 6
42 Runtime error 2 ms 592 KB Execution killed with signal 6
43 Execution timed out 1080 ms 8016 KB Time limit exceeded
44 Runtime error 167 ms 1096 KB Execution killed with signal 6
45 Execution timed out 1086 ms 7956 KB Time limit exceeded
46 Correct 76 ms 8016 KB Output is correct
47 Execution timed out 1076 ms 8016 KB Time limit exceeded
48 Execution timed out 1066 ms 8016 KB Time limit exceeded
49 Runtime error 31 ms 15952 KB Execution killed with signal 6
50 Execution timed out 1067 ms 8008 KB Time limit exceeded
51 Execution timed out 1053 ms 8016 KB Time limit exceeded
52 Execution timed out 1062 ms 7968 KB Time limit exceeded
53 Execution timed out 1053 ms 8016 KB Time limit exceeded
54 Execution timed out 1062 ms 8016 KB Time limit exceeded
55 Execution timed out 1036 ms 8016 KB Time limit exceeded
56 Correct 46 ms 8008 KB Output is correct
57 Execution timed out 1077 ms 7864 KB Time limit exceeded
58 Execution timed out 1061 ms 8016 KB Time limit exceeded
59 Execution timed out 1053 ms 8016 KB Time limit exceeded
60 Execution timed out 1046 ms 8016 KB Time limit exceeded
61 Runtime error 31 ms 15952 KB Execution killed with signal 6
62 Runtime error 31 ms 16024 KB Execution killed with signal 6
63 Runtime error 32 ms 15948 KB Execution killed with signal 6
64 Runtime error 83 ms 16028 KB Execution killed with signal 6
65 Execution timed out 1057 ms 8016 KB Time limit exceeded
66 Execution timed out 1064 ms 8016 KB Time limit exceeded
67 Execution timed out 1065 ms 7960 KB Time limit exceeded
68 Execution timed out 1071 ms 8084 KB Time limit exceeded
69 Execution timed out 1064 ms 8028 KB Time limit exceeded
70 Execution timed out 1057 ms 5200 KB Time limit exceeded
71 Runtime error 408 ms 16028 KB Execution killed with signal 6
72 Execution timed out 1054 ms 8016 KB Time limit exceeded
73 Execution timed out 1059 ms 8016 KB Time limit exceeded
74 Runtime error 533 ms 15948 KB Execution killed with signal 6
75 Runtime error 722 ms 16024 KB Execution killed with signal 6
76 Execution timed out 1044 ms 8016 KB Time limit exceeded
77 Execution timed out 1060 ms 8016 KB Time limit exceeded
78 Execution timed out 1067 ms 8016 KB Time limit exceeded
79 Runtime error 30 ms 15952 KB Execution killed with signal 6
80 Runtime error 36 ms 15960 KB Execution killed with signal 6
81 Runtime error 69 ms 15948 KB Execution killed with signal 6
82 Execution timed out 1073 ms 8016 KB Time limit exceeded
83 Runtime error 856 ms 16020 KB Execution killed with signal 6
84 Runtime error 28 ms 15952 KB Execution killed with signal 6
85 Execution timed out 1079 ms 8016 KB Time limit exceeded
86 Execution timed out 1073 ms 8016 KB Time limit exceeded
87 Execution timed out 1047 ms 8016 KB Time limit exceeded
88 Execution timed out 1062 ms 8016 KB Time limit exceeded
89 Execution timed out 1079 ms 8016 KB Time limit exceeded
90 Execution timed out 1067 ms 5200 KB Time limit exceeded
91 Execution timed out 1057 ms 7952 KB Time limit exceeded
92 Execution timed out 1081 ms 8016 KB Time limit exceeded
93 Execution timed out 1058 ms 7956 KB Time limit exceeded
94 Execution timed out 1065 ms 7952 KB Time limit exceeded
95 Runtime error 882 ms 16032 KB Execution killed with signal 6
96 Execution timed out 1075 ms 8016 KB Time limit exceeded
97 Execution timed out 1054 ms 8016 KB Time limit exceeded
98 Execution timed out 1073 ms 8016 KB Time limit exceeded
99 Execution timed out 1071 ms 8016 KB Time limit exceeded
100 Execution timed out 1056 ms 8016 KB Time limit exceeded