답안 #907304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
907304	2024-01-15T11:05:26 Z	daoquanglinh2007	Bomb (IZhO17_bomb)	C++17	51 / 100	982 ms	55892 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 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;
}

Subtask #1

51.0 / 100.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