답안 #524025

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524025 2022-02-08T14:32:18 Z boykut Bomb (IZhO17_bomb) C++14
21 / 100
1000 ms 55044 KB
#include <bits/stdc++.h>

using namespace std;

const int N = 2500;
int arr[N][N];
int pref[N][N];

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

	int n, m;
	cin >> n >> m;
	if (n * n * n * m * m * m > 1e8) return 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char x; cin >> x;
			arr[i][j] = x - '0';
			pref[i][j] = x - '0';
			pref[i][j] += (i ? pref[i - 1][j] : 0);
			pref[i][j] += (j ? pref[i][j - 1] : 0);
			pref[i][j] -= (i && j ? pref[i - 1][j - 1] : 0);
		}
	}

	auto get = [&](int a, int b, int c, int d) ->int {
		int s = pref[c][d];
		s -= (a ? pref[a - 1][d] : 0);
		s -= (b ? pref[c][b - 1] : 0);
		s += (a && b ? pref[a - 1][b - 1] : 0);
		return s;
	};

	// brute force
	int ans = 0, Q = 2;
	for (int a = 1; a <= n; a++) {
		for (int b = 1; b <= m; b++) {
			for (int i = 0; i + a - 1 < n; i++) {
				for (int j = 0; j + b - 1 < m; j++) {
					int g = get(i, j, i + a - 1, j + b - 1);
					if (g == a * b) {
						for (int i2 = i; i2 <= i + a - 1; i2++) {
							for (int j2 = j; j2 <= j + b - 1; j2++)
								arr[i2][j2] = Q;
						}
					}
				}
			}
			int ok = 1;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (arr[i][j] != 0 && arr[i][j] != Q) ok = 0;
				}
			}
			if (ok) {
				ans = max(ans, a * b);
			}
			Q++;
		}
	}
	cout << ans << '\n';

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Execution timed out 1093 ms 20404 KB Time limit exceeded
4 Correct 350 ms 20388 KB Output is correct
5 Correct 40 ms 332 KB Output is correct
6 Incorrect 1 ms 204 KB Output isn't correct
7 Correct 1 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 332 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 52 ms 872 KB Output is correct
18 Incorrect 1 ms 204 KB Output isn't correct
19 Correct 85 ms 1128 KB Output is correct
20 Incorrect 1 ms 324 KB Output isn't correct
21 Incorrect 1 ms 204 KB Output isn't correct
22 Incorrect 1 ms 204 KB Output isn't correct
23 Correct 175 ms 1192 KB Output is correct
24 Incorrect 1 ms 204 KB Output isn't correct
25 Correct 232 ms 1192 KB Output is correct
26 Execution timed out 1083 ms 1100 KB Time limit exceeded
27 Incorrect 0 ms 332 KB Output isn't correct
28 Incorrect 1 ms 332 KB Output isn't correct
29 Incorrect 1 ms 332 KB Output isn't correct
30 Execution timed out 1080 ms 5316 KB Time limit exceeded
31 Execution timed out 1081 ms 4300 KB Time limit exceeded
32 Execution timed out 1002 ms 4928 KB Time limit exceeded
33 Incorrect 1 ms 332 KB Output isn't correct
34 Execution timed out 1088 ms 3788 KB Time limit exceeded
35 Incorrect 1 ms 332 KB Output isn't correct
36 Incorrect 0 ms 332 KB Output isn't correct
37 Correct 1 ms 460 KB Output is correct
38 Execution timed out 1036 ms 52360 KB Time limit exceeded
39 Correct 1 ms 460 KB Output is correct
40 Incorrect 1 ms 332 KB Output isn't correct
41 Correct 1 ms 444 KB Output is correct
42 Execution timed out 1078 ms 1100 KB Time limit exceeded
43 Execution timed out 1033 ms 52468 KB Time limit exceeded
44 Incorrect 1 ms 332 KB Output isn't correct
45 Execution timed out 1052 ms 52872 KB Time limit exceeded
46 Execution timed out 1061 ms 53280 KB Time limit exceeded
47 Execution timed out 1060 ms 53240 KB Time limit exceeded
48 Execution timed out 1082 ms 53260 KB Time limit exceeded
49 Execution timed out 1046 ms 53224 KB Time limit exceeded
50 Execution timed out 1037 ms 53196 KB Time limit exceeded
51 Execution timed out 1049 ms 53376 KB Time limit exceeded
52 Execution timed out 1026 ms 53444 KB Time limit exceeded
53 Execution timed out 1022 ms 53660 KB Time limit exceeded
54 Execution timed out 1075 ms 53760 KB Time limit exceeded
55 Execution timed out 1085 ms 53872 KB Time limit exceeded
56 Execution timed out 1103 ms 54116 KB Time limit exceeded
57 Execution timed out 1076 ms 54256 KB Time limit exceeded
58 Execution timed out 1056 ms 54264 KB Time limit exceeded
59 Execution timed out 1060 ms 54512 KB Time limit exceeded
60 Execution timed out 1068 ms 54596 KB Time limit exceeded
61 Execution timed out 1071 ms 54492 KB Time limit exceeded
62 Execution timed out 1089 ms 54728 KB Time limit exceeded
63 Execution timed out 1087 ms 54828 KB Time limit exceeded
64 Execution timed out 1077 ms 54752 KB Time limit exceeded
65 Execution timed out 1066 ms 54668 KB Time limit exceeded
66 Execution timed out 1086 ms 54724 KB Time limit exceeded
67 Execution timed out 1070 ms 54724 KB Time limit exceeded
68 Execution timed out 1073 ms 54564 KB Time limit exceeded
69 Execution timed out 1086 ms 54300 KB Time limit exceeded
70 Execution timed out 1091 ms 43324 KB Time limit exceeded
71 Execution timed out 1072 ms 53900 KB Time limit exceeded
72 Execution timed out 1094 ms 53916 KB Time limit exceeded
73 Execution timed out 1082 ms 53444 KB Time limit exceeded
74 Execution timed out 1098 ms 53512 KB Time limit exceeded
75 Execution timed out 1081 ms 53444 KB Time limit exceeded
76 Execution timed out 1091 ms 52952 KB Time limit exceeded
77 Execution timed out 1055 ms 52972 KB Time limit exceeded
78 Execution timed out 1098 ms 52984 KB Time limit exceeded
79 Execution timed out 1073 ms 52536 KB Time limit exceeded
80 Execution timed out 1099 ms 52412 KB Time limit exceeded
81 Execution timed out 1087 ms 52300 KB Time limit exceeded
82 Execution timed out 1091 ms 51904 KB Time limit exceeded
83 Execution timed out 1085 ms 51580 KB Time limit exceeded
84 Execution timed out 1074 ms 51588 KB Time limit exceeded
85 Execution timed out 1038 ms 51736 KB Time limit exceeded
86 Execution timed out 1098 ms 55020 KB Time limit exceeded
87 Execution timed out 1091 ms 55044 KB Time limit exceeded
88 Execution timed out 1071 ms 54844 KB Time limit exceeded
89 Execution timed out 1085 ms 54812 KB Time limit exceeded
90 Execution timed out 1093 ms 43256 KB Time limit exceeded
91 Execution timed out 1088 ms 54340 KB Time limit exceeded
92 Execution timed out 1086 ms 54316 KB Time limit exceeded
93 Execution timed out 1075 ms 54136 KB Time limit exceeded
94 Execution timed out 1071 ms 53956 KB Time limit exceeded
95 Execution timed out 1038 ms 53784 KB Time limit exceeded
96 Execution timed out 1065 ms 53568 KB Time limit exceeded
97 Execution timed out 1074 ms 53800 KB Time limit exceeded
98 Execution timed out 1074 ms 54088 KB Time limit exceeded
99 Execution timed out 1074 ms 54068 KB Time limit exceeded
100 Execution timed out 1078 ms 53828 KB Time limit exceeded