oj.uz

답안 #907370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907370 2024-01-15T12:37:44 Z daoquanglinh2007 Bomb (IZhO17_bomb) C++17
72 / 100
 968 ms 55900 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse4")

#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];
			
	if (N <= 450 && M <= 450){
		int j = W;
		for (int i = 1; i <= H; i++){
			while (j > 0 && !check(i, j)) j--;
			ans = max(ans, i*j);
		}
		cout << ans;
		return 0;
	}
			
	int l = 1, r = W;
	while (l <= r){
		int mid = (l+r)/2;
		if (check(H, mid)){
			ans = max(ans, H*mid);
			l = mid+1;
		}
		else{
			if (H-1 > 0 && check(H-1, mid)) ans = max(ans, (H-1)*mid);
			r = mid-1;
		}
	}
	l = 1, r = H;
	while (l <= r){
		int mid = (l+r)/2;
		if (check(mid, W)){
			ans = max(ans, mid*W);
			l = mid+1;
		}
		else r = mid-1;
	}
	int j = W-1;
	for (int i = 1; i < H; i++){
		if (i*j <= ans) continue;
		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;
}

Subtask #1
72.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 9 ms 54620 KB Output is correct
4 Correct 9 ms 54620 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 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 4440 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 3 ms 10844 KB Output is correct
21 Correct 2 ms 6748 KB Output is correct
22 Correct 2 ms 10840 KB Output is correct
23 Correct 3 ms 10844 KB Output is correct
24 Correct 3 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 7 ms 13148 KB Output is correct
29 Correct 38 ms 14936 KB Output is correct
30 Correct 98 ms 14936 KB Output is correct
31 Correct 55 ms 13656 KB Output is correct
32 Correct 60 ms 14992 KB Output is correct
33 Correct 114 ms 17072 KB Output is correct
34 Correct 7 ms 13404 KB Output is correct
35 Correct 48 ms 16220 KB Output is correct
36 Correct 31 ms 19192 KB Output is correct
37 Correct 2 ms 6488 KB Output is correct
38 Correct 296 ms 55632 KB Output is correct
39 Correct 1 ms 6492 KB Output is correct
40 Correct 232 ms 27308 KB Output is correct
41 Correct 1 ms 6492 KB Output is correct
42 Correct 4 ms 10844 KB Output is correct
43 Correct 433 ms 55636 KB Output is correct
44 Correct 150 ms 19088 KB Output is correct
45 Incorrect 959 ms 55716 KB Output isn't correct
46 Correct 276 ms 55636 KB Output is correct
47 Incorrect 951 ms 55684 KB Output isn't correct
48 Correct 708 ms 55652 KB Output is correct
49 Correct 203 ms 55656 KB Output is correct
50 Correct 736 ms 55660 KB Output is correct
51 Correct 734 ms 55656 KB Output is correct
52 Correct 688 ms 55656 KB Output is correct
53 Correct 695 ms 55892 KB Output is correct
54 Correct 951 ms 55708 KB Output is correct
55 Correct 956 ms 55660 KB Output is correct
56 Correct 292 ms 55692 KB Output is correct
57 Correct 941 ms 55696 KB Output is correct
58 Correct 964 ms 55892 KB Output is correct
59 Correct 965 ms 55720 KB Output is correct
60 Correct 272 ms 55712 KB Output is correct
61 Correct 271 ms 55656 KB Output is correct
62 Correct 358 ms 55608 KB Output is correct
63 Correct 359 ms 55424 KB Output is correct
64 Correct 348 ms 55636 KB Output is correct
65 Correct 650 ms 55652 KB Output is correct
66 Correct 315 ms 55656 KB Output is correct
67 Correct 799 ms 55724 KB Output is correct
68 Correct 826 ms 55688 KB Output is correct
69 Correct 783 ms 55652 KB Output is correct
70 Incorrect 952 ms 48704 KB Output isn't correct
71 Incorrect 954 ms 55700 KB Output isn't correct
72 Incorrect 960 ms 55664 KB Output isn't correct
73 Incorrect 956 ms 55432 KB Output isn't correct
74 Incorrect 952 ms 55684 KB Output isn't correct
75 Incorrect 957 ms 55888 KB Output isn't correct
76 Incorrect 956 ms 55660 KB Output isn't correct
77 Incorrect 958 ms 55660 KB Output isn't correct
78 Incorrect 954 ms 55656 KB Output isn't correct
79 Incorrect 958 ms 55660 KB Output isn't correct
80 Incorrect 959 ms 55660 KB Output isn't correct
81 Incorrect 958 ms 55888 KB Output isn't correct
82 Incorrect 961 ms 55892 KB Output isn't correct
83 Incorrect 954 ms 55900 KB Output isn't correct
84 Incorrect 961 ms 55700 KB Output isn't correct
85 Incorrect 951 ms 55656 KB Output isn't correct
86 Correct 960 ms 55892 KB Output is correct
87 Correct 960 ms 55656 KB Output is correct
88 Incorrect 957 ms 55656 KB Output isn't correct
89 Incorrect 958 ms 55656 KB Output isn't correct
90 Incorrect 950 ms 49872 KB Output isn't correct
91 Incorrect 960 ms 55656 KB Output isn't correct
92 Incorrect 959 ms 55656 KB Output isn't correct
93 Correct 962 ms 55656 KB Output is correct
94 Incorrect 951 ms 55892 KB Output isn't correct
95 Incorrect 958 ms 55692 KB Output isn't correct
96 Incorrect 954 ms 55660 KB Output isn't correct
97 Correct 951 ms 55656 KB Output is correct
98 Incorrect 968 ms 55836 KB Output isn't correct
99 Incorrect 957 ms 55660 KB Output isn't correct
100 Correct 953 ms 55696 KB Output is correct