답안 #907304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907304 2024-01-15T11:05:26 Z daoquanglinh2007 Bomb (IZhO17_bomb) C++17
51 / 100
982 ms 55892 KB
#include <bits/stdc++.h>
using namespace std;
 
const int NM = 2500, inf = 1e9+7;
 
int N, M, f[NM+5][NM+5], dp[NM+5][NM+5], ans = 0, H = +inf, W = +inf;
char a[NM+5][NM+5];
 
int getf(int x, int y, int u, int v){
	return f[u][v]-f[x-1][v]-f[u][y-1]+f[x-1][y-1];
}
 
bool check(int r, int c){
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++) dp[i][j] = 0;
	
	for (int i = 1; i+r-1 <= N; i++)
		for (int j = 1; j+c-1 <= M; j++)
			if (getf(i, j, i+r-1, j+c-1) == r*c){
				dp[i][j]++;
				dp[i+r][j]--;
				dp[i][j+c]--;
				dp[i+r][j+c]++;
			}
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++){
			dp[i][j] += dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
			if (dp[i][j] == 0 && a[i][j] == '1') return 0;
		}
	return 1;
}
 
void preprocess(){
	for (int j = 1; j <= M; j++)
		for (int i = 1; i <= N; i++){
			if (a[i][j] == '0') continue;
			int k = i;
			while (k <= N && a[k][j] == '1') k++;
			H = min(H, k-i);
			i = k-1;
		}
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++){
			if (a[i][j] == '0') continue;
			int k = j;
			while (k <= M && a[i][k] == '1') k++;
			W = min(W, k-j);
			j = k-1;
		}
}
 
int main(){
//	freopen("BOMB.inp", "r", stdin);
//	freopen("BOMB.ans", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++){
			cin >> a[i][j];
			if (a[i][j] == '1') f[i][j] = 1;
		}
	preprocess();
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			f[i][j] += f[i][j-1]+f[i-1][j]-f[i-1][j-1];
			
	int j = W;
	for (int i = 1; i <= H; i++){
		while (j >= 0 && !check(i, j)){
			if ((double)clock()/CLOCKS_PER_SEC > 0.95) break;
			j--;
		}
		if ((double)clock()/CLOCKS_PER_SEC > 0.95) break;
		ans = max(ans, i*j);
	}
	cout << ans;
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 10 ms 54632 KB Output is correct
4 Correct 10 ms 54448 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 1 ms 4612 KB Output is correct
9 Correct 1 ms 4444 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 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 2 ms 6492 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 3 ms 10840 KB Output is correct
21 Correct 2 ms 6748 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Correct 3 ms 10844 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 4 ms 10844 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 4 ms 14940 KB Output is correct
28 Correct 8 ms 14936 KB Output is correct
29 Correct 53 ms 14940 KB Output is correct
30 Correct 131 ms 15192 KB Output is correct
31 Correct 80 ms 14940 KB Output is correct
32 Correct 99 ms 14988 KB Output is correct
33 Correct 183 ms 17068 KB Output is correct
34 Correct 7 ms 13460 KB Output is correct
35 Correct 50 ms 16988 KB Output is correct
36 Correct 51 ms 19032 KB Output is correct
37 Correct 1 ms 6492 KB Output is correct
38 Incorrect 968 ms 55612 KB Output isn't correct
39 Correct 1 ms 6492 KB Output is correct
40 Correct 951 ms 27296 KB Output is correct
41 Correct 1 ms 6492 KB Output is correct
42 Correct 5 ms 10904 KB Output is correct
43 Incorrect 982 ms 55656 KB Output isn't correct
44 Correct 234 ms 19036 KB Output is correct
45 Incorrect 961 ms 55656 KB Output isn't correct
46 Correct 831 ms 55656 KB Output is correct
47 Incorrect 970 ms 55696 KB Output isn't correct
48 Incorrect 954 ms 55708 KB Output isn't correct
49 Correct 299 ms 55616 KB Output is correct
50 Incorrect 962 ms 55652 KB Output isn't correct
51 Incorrect 979 ms 55700 KB Output isn't correct
52 Incorrect 962 ms 55656 KB Output isn't correct
53 Incorrect 973 ms 55656 KB Output isn't correct
54 Incorrect 951 ms 55656 KB Output isn't correct
55 Incorrect 968 ms 55656 KB Output isn't correct
56 Incorrect 951 ms 55656 KB Output isn't correct
57 Incorrect 952 ms 55656 KB Output isn't correct
58 Incorrect 956 ms 55652 KB Output isn't correct
59 Incorrect 964 ms 55684 KB Output isn't correct
60 Incorrect 978 ms 55660 KB Output isn't correct
61 Correct 637 ms 55656 KB Output is correct
62 Incorrect 960 ms 55660 KB Output isn't correct
63 Incorrect 952 ms 55656 KB Output isn't correct
64 Incorrect 961 ms 55652 KB Output isn't correct
65 Incorrect 970 ms 55892 KB Output isn't correct
66 Correct 444 ms 55544 KB Output is correct
67 Incorrect 970 ms 55892 KB Output isn't correct
68 Incorrect 953 ms 55656 KB Output isn't correct
69 Incorrect 968 ms 55660 KB Output isn't correct
70 Incorrect 957 ms 49868 KB Output isn't correct
71 Incorrect 965 ms 55888 KB Output isn't correct
72 Incorrect 957 ms 55656 KB Output isn't correct
73 Incorrect 953 ms 55656 KB Output isn't correct
74 Incorrect 958 ms 55656 KB Output isn't correct
75 Incorrect 958 ms 55652 KB Output isn't correct
76 Incorrect 968 ms 55888 KB Output isn't correct
77 Incorrect 965 ms 55660 KB Output isn't correct
78 Incorrect 967 ms 55464 KB Output isn't correct
79 Incorrect 956 ms 55808 KB Output isn't correct
80 Incorrect 962 ms 55692 KB Output isn't correct
81 Incorrect 950 ms 55696 KB Output isn't correct
82 Incorrect 954 ms 55888 KB Output isn't correct
83 Incorrect 965 ms 55888 KB Output isn't correct
84 Incorrect 954 ms 55892 KB Output isn't correct
85 Incorrect 955 ms 55652 KB Output isn't correct
86 Correct 950 ms 55892 KB Output is correct
87 Correct 958 ms 55888 KB Output is correct
88 Incorrect 955 ms 55632 KB Output isn't correct
89 Incorrect 962 ms 55856 KB Output isn't correct
90 Incorrect 954 ms 49824 KB Output isn't correct
91 Incorrect 953 ms 55888 KB Output isn't correct
92 Incorrect 958 ms 55652 KB Output isn't correct
93 Correct 960 ms 55892 KB Output is correct
94 Incorrect 953 ms 55652 KB Output isn't correct
95 Incorrect 968 ms 55652 KB Output isn't correct
96 Incorrect 962 ms 55656 KB Output isn't correct
97 Correct 950 ms 55800 KB Output is correct
98 Incorrect 963 ms 55656 KB Output isn't correct
99 Incorrect 957 ms 55660 KB Output isn't correct
100 Correct 955 ms 55632 KB Output is correct