답안 #907300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
907300	2024-01-15T11:03:14 Z	daoquanglinh2007	Bomb (IZhO17_bomb)	C++17	46 / 100	622 ms	55904 KB

bomb

#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 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 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;
	}
	cout << ans;
	return 0;
}

Subtask #1

46.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4440 KB	Output is correct
3	Correct	10 ms	54620 KB	Output is correct
4	Correct	10 ms	54616 KB	Output is correct
5	Correct	2 ms	4440 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Incorrect	1 ms	4444 KB	Output isn't correct
9	Incorrect	1 ms	4444 KB	Output isn't correct
10	Correct	1 ms	4444 KB	Output is correct
11	Incorrect	1 ms	4440 KB	Output isn't correct
12	Correct	1 ms	4440 KB	Output is correct
13	Correct	2 ms	4444 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Incorrect	2 ms	4444 KB	Output isn't correct
16	Correct	2 ms	6492 KB	Output is correct
17	Correct	2 ms	8796 KB	Output is correct
18	Incorrect	2 ms	8792 KB	Output isn't correct
19	Incorrect	2 ms	10840 KB	Output isn't correct
20	Incorrect	3 ms	10844 KB	Output isn't correct
21	Incorrect	2 ms	6748 KB	Output isn't correct
22	Incorrect	3 ms	10844 KB	Output isn't correct
23	Incorrect	2 ms	10844 KB	Output isn't correct
24	Incorrect	2 ms	10844 KB	Output isn't correct
25	Incorrect	2 ms	10840 KB	Output isn't correct
26	Correct	3 ms	10840 KB	Output is correct
27	Correct	5 ms	14940 KB	Output is correct
28	Incorrect	6 ms	14808 KB	Output isn't correct
29	Incorrect	8 ms	14940 KB	Output isn't correct
30	Incorrect	10 ms	14936 KB	Output isn't correct
31	Incorrect	9 ms	14940 KB	Output isn't correct
32	Incorrect	9 ms	14940 KB	Output isn't correct
33	Incorrect	13 ms	17092 KB	Output isn't correct
34	Incorrect	5 ms	13400 KB	Output isn't correct
35	Incorrect	9 ms	16988 KB	Output isn't correct
36	Correct	16 ms	19032 KB	Output is correct
37	Correct	2 ms	6488 KB	Output is correct
38	Correct	570 ms	55652 KB	Output is correct
39	Correct	2 ms	6488 KB	Output is correct
40	Correct	44 ms	27228 KB	Output is correct
41	Correct	2 ms	6492 KB	Output is correct
42	Incorrect	2 ms	10904 KB	Output isn't correct
43	Correct	622 ms	55656 KB	Output is correct
44	Incorrect	12 ms	19036 KB	Output isn't correct
45	Incorrect	364 ms	55656 KB	Output isn't correct
46	Correct	375 ms	55656 KB	Output is correct
47	Incorrect	393 ms	55716 KB	Output isn't correct
48	Correct	363 ms	55656 KB	Output is correct
49	Correct	263 ms	55656 KB	Output is correct
50	Correct	393 ms	55636 KB	Output is correct
51	Correct	389 ms	55464 KB	Output is correct
52	Correct	362 ms	55656 KB	Output is correct
53	Correct	360 ms	55720 KB	Output is correct
54	Correct	372 ms	55452 KB	Output is correct
55	Correct	378 ms	55464 KB	Output is correct
56	Correct	479 ms	55656 KB	Output is correct
57	Correct	431 ms	55632 KB	Output is correct
58	Correct	444 ms	55660 KB	Output is correct
59	Correct	402 ms	55732 KB	Output is correct
60	Correct	385 ms	55652 KB	Output is correct
61	Correct	384 ms	55448 KB	Output is correct
62	Correct	561 ms	55660 KB	Output is correct
63	Correct	616 ms	55772 KB	Output is correct
64	Correct	518 ms	55632 KB	Output is correct
65	Correct	321 ms	55632 KB	Output is correct
66	Correct	381 ms	55904 KB	Output is correct
67	Correct	366 ms	55656 KB	Output is correct
68	Correct	437 ms	55636 KB	Output is correct
69	Correct	420 ms	55636 KB	Output is correct
70	Incorrect	226 ms	49872 KB	Output isn't correct
71	Incorrect	358 ms	55644 KB	Output isn't correct
72	Incorrect	375 ms	55668 KB	Output isn't correct
73	Incorrect	352 ms	55656 KB	Output isn't correct
74	Incorrect	379 ms	55652 KB	Output isn't correct
75	Incorrect	426 ms	55444 KB	Output isn't correct
76	Incorrect	404 ms	55656 KB	Output isn't correct
77	Incorrect	406 ms	55660 KB	Output isn't correct
78	Incorrect	410 ms	55728 KB	Output isn't correct
79	Incorrect	260 ms	55632 KB	Output isn't correct
80	Incorrect	261 ms	55680 KB	Output isn't correct
81	Incorrect	289 ms	55456 KB	Output isn't correct
82	Incorrect	412 ms	55652 KB	Output isn't correct
83	Incorrect	413 ms	55636 KB	Output isn't correct
84	Incorrect	256 ms	55436 KB	Output isn't correct
85	Incorrect	379 ms	55656 KB	Output isn't correct
86	Incorrect	254 ms	55660 KB	Output isn't correct
87	Correct	383 ms	55456 KB	Output is correct
88	Incorrect	381 ms	55656 KB	Output isn't correct
89	Incorrect	325 ms	55652 KB	Output isn't correct
90	Incorrect	256 ms	49744 KB	Output isn't correct
91	Incorrect	376 ms	55660 KB	Output isn't correct
92	Incorrect	342 ms	55660 KB	Output isn't correct
93	Incorrect	263 ms	55636 KB	Output isn't correct
94	Incorrect	329 ms	55660 KB	Output isn't correct
95	Incorrect	414 ms	55708 KB	Output isn't correct
96	Incorrect	386 ms	55652 KB	Output isn't correct
97	Incorrect	257 ms	55608 KB	Output isn't correct
98	Incorrect	420 ms	55636 KB	Output isn't correct
99	Incorrect	330 ms	55632 KB	Output isn't correct
100	Incorrect	261 ms	55632 KB	Output isn't correct