Submission #907289

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
907289	2024-01-15T10:54:49 Z	daoquanglinh2007	Bomb (IZhO17_bomb)	C++17	32 / 100	1000 ms	59064 KB

bomb

#include <bits/stdc++.h>
using namespace std;

const int NM = 2500;

int N, M, f[NM+5][NM+5], dp[NM+5][NM+5], ans = 0;
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;
}

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;
		}
	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 = M;
	for (int i = 1; i <= N; i++){
		while (j >= 0 && !check(i, j)){
			j--;
			if (i*j <= ans) break;
		}
		if (i*j <= ans) break;
		ans = i*j;
	}
	cout << ans;
	return 0;
}

Subtask #1

32.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	10 ms	54480 KB	Output is correct
4	Correct	10 ms	54620 KB	Output is correct
5	Correct	5 ms	4444 KB	Output is correct
6	Correct	2 ms	4444 KB	Output is correct
7	Correct	1 ms	4440 KB	Output is correct
8	Correct	1 ms	4696 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	4440 KB	Output is correct
15	Correct	1 ms	4440 KB	Output is correct
16	Correct	2 ms	6744 KB	Output is correct
17	Correct	2 ms	8660 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	10844 KB	Output is correct
21	Correct	2 ms	6748 KB	Output is correct
22	Correct	3 ms	10844 KB	Output is correct
23	Correct	3 ms	10840 KB	Output is correct
24	Incorrect	2 ms	10904 KB	Output isn't correct
25	Incorrect	3 ms	10844 KB	Output isn't correct
26	Correct	4 ms	10840 KB	Output is correct
27	Correct	21 ms	14940 KB	Output is correct
28	Correct	31 ms	14936 KB	Output is correct
29	Incorrect	42 ms	14936 KB	Output isn't correct
30	Incorrect	58 ms	15164 KB	Output isn't correct
31	Incorrect	47 ms	14940 KB	Output isn't correct
32	Incorrect	47 ms	14936 KB	Output isn't correct
33	Correct	72 ms	17244 KB	Output is correct
34	Correct	21 ms	13400 KB	Output is correct
35	Incorrect	49 ms	17244 KB	Output isn't correct
36	Correct	147 ms	19288 KB	Output is correct
37	Correct	2 ms	6492 KB	Output is correct
38	Execution timed out	1056 ms	58916 KB	Time limit exceeded
39	Correct	1 ms	6488 KB	Output is correct
40	Correct	678 ms	28048 KB	Output is correct
41	Incorrect	2 ms	6492 KB	Output isn't correct
42	Incorrect	3 ms	10844 KB	Output isn't correct
43	Execution timed out	1086 ms	58964 KB	Time limit exceeded
44	Incorrect	71 ms	19288 KB	Output isn't correct
45	Execution timed out	1054 ms	58964 KB	Time limit exceeded
46	Execution timed out	1024 ms	58756 KB	Time limit exceeded
47	Execution timed out	1096 ms	58960 KB	Time limit exceeded
48	Execution timed out	1063 ms	58964 KB	Time limit exceeded
49	Execution timed out	1024 ms	58960 KB	Time limit exceeded
50	Execution timed out	1101 ms	58956 KB	Time limit exceeded
51	Execution timed out	1043 ms	58768 KB	Time limit exceeded
52	Execution timed out	1020 ms	58768 KB	Time limit exceeded
53	Execution timed out	1049 ms	58764 KB	Time limit exceeded
54	Execution timed out	1020 ms	58960 KB	Time limit exceeded
55	Execution timed out	1016 ms	58772 KB	Time limit exceeded
56	Execution timed out	1006 ms	58960 KB	Time limit exceeded
57	Execution timed out	1055 ms	58788 KB	Time limit exceeded
58	Execution timed out	1047 ms	58996 KB	Time limit exceeded
59	Execution timed out	1054 ms	58964 KB	Time limit exceeded
60	Execution timed out	1030 ms	58960 KB	Time limit exceeded
61	Execution timed out	1012 ms	58756 KB	Time limit exceeded
62	Execution timed out	1039 ms	58936 KB	Time limit exceeded
63	Execution timed out	1051 ms	58964 KB	Time limit exceeded
64	Execution timed out	1010 ms	58964 KB	Time limit exceeded
65	Execution timed out	1072 ms	58772 KB	Time limit exceeded
66	Execution timed out	1076 ms	58756 KB	Time limit exceeded
67	Execution timed out	1010 ms	58788 KB	Time limit exceeded
68	Execution timed out	1086 ms	58784 KB	Time limit exceeded
69	Execution timed out	1071 ms	59008 KB	Time limit exceeded
70	Execution timed out	1064 ms	52116 KB	Time limit exceeded
71	Execution timed out	1046 ms	58888 KB	Time limit exceeded
72	Execution timed out	1059 ms	58780 KB	Time limit exceeded
73	Execution timed out	1039 ms	58760 KB	Time limit exceeded
74	Execution timed out	1076 ms	58788 KB	Time limit exceeded
75	Execution timed out	1058 ms	58864 KB	Time limit exceeded
76	Execution timed out	1014 ms	58772 KB	Time limit exceeded
77	Execution timed out	1064 ms	58880 KB	Time limit exceeded
78	Execution timed out	1046 ms	58964 KB	Time limit exceeded
79	Execution timed out	1072 ms	58740 KB	Time limit exceeded
80	Execution timed out	1038 ms	58768 KB	Time limit exceeded
81	Execution timed out	1018 ms	58784 KB	Time limit exceeded
82	Execution timed out	1099 ms	58896 KB	Time limit exceeded
83	Execution timed out	1018 ms	58764 KB	Time limit exceeded
84	Execution timed out	1025 ms	58860 KB	Time limit exceeded
85	Execution timed out	1051 ms	58868 KB	Time limit exceeded
86	Execution timed out	1031 ms	58960 KB	Time limit exceeded
87	Execution timed out	1097 ms	58756 KB	Time limit exceeded
88	Execution timed out	1054 ms	58880 KB	Time limit exceeded
89	Execution timed out	1057 ms	58940 KB	Time limit exceeded
90	Execution timed out	1058 ms	52052 KB	Time limit exceeded
91	Execution timed out	1059 ms	58780 KB	Time limit exceeded
92	Execution timed out	1056 ms	58964 KB	Time limit exceeded
93	Execution timed out	1050 ms	59064 KB	Time limit exceeded
94	Execution timed out	1034 ms	58960 KB	Time limit exceeded
95	Execution timed out	1052 ms	58800 KB	Time limit exceeded
96	Execution timed out	1040 ms	58768 KB	Time limit exceeded
97	Execution timed out	1024 ms	58960 KB	Time limit exceeded
98	Execution timed out	1101 ms	58868 KB	Time limit exceeded
99	Execution timed out	1043 ms	58936 KB	Time limit exceeded
100	Execution timed out	1008 ms	58960 KB	Time limit exceeded