oj.uz

Submission #907308

# Submission time Handle Problem Language Result Execution time Memory
907308 2024-01-15T11:13:09 Z daoquanglinh2007 Bomb (IZhO17_bomb) C++17
58 / 100
 1000 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];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int get_rand(int l, int r){
	int tmp = rng()%(r-l+1);
	if (tmp < 0) tmp += r-l+1;
	return l + tmp;
}
 
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;
		}
}

void solve(int h){
	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;
		}
	}
}
 
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;
	}
			
	solve(H);
	for (int i = 1; i <= 3; i++){
		int h = get_rand(1, H);
		solve(h);
	}
	cout << ans;
	return 0;
}

Subtask #1
58.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 9 ms 54620 KB Output is correct
4 Correct 9 ms 54672 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4440 KB Output is correct
7 Correct 2 ms 4440 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 6488 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 4696 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 4 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 5 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 4 ms 10844 KB Output is correct
27 Correct 6 ms 14936 KB Output is correct
28 Correct 9 ms 13148 KB Output is correct
29 Correct 55 ms 14940 KB Output is correct
30 Correct 136 ms 14940 KB Output is correct
31 Correct 110 ms 13508 KB Output is correct
32 Correct 96 ms 15188 KB Output is correct
33 Correct 177 ms 17068 KB Output is correct
34 Correct 8 ms 13404 KB Output is correct
35 Correct 55 ms 16216 KB Output is correct
36 Correct 51 ms 19088 KB Output is correct
37 Correct 2 ms 6488 KB Output is correct
38 Execution timed out 1024 ms 55632 KB Time limit exceeded
39 Correct 2 ms 6488 KB Output is correct
40 Incorrect 105 ms 27288 KB Output isn't correct
41 Correct 2 ms 6492 KB Output is correct
42 Correct 5 ms 10844 KB Output is correct
43 Execution timed out 1057 ms 55448 KB Time limit exceeded
44 Correct 260 ms 19084 KB Output is correct
45 Incorrect 920 ms 55656 KB Output isn't correct
46 Correct 687 ms 55656 KB Output is correct
47 Incorrect 958 ms 55520 KB Output isn't correct
48 Correct 834 ms 55656 KB Output is correct
49 Correct 450 ms 55452 KB Output is correct
50 Correct 963 ms 55656 KB Output is correct
51 Correct 974 ms 55664 KB Output is correct
52 Correct 849 ms 55660 KB Output is correct
53 Correct 809 ms 55664 KB Output is correct
54 Correct 858 ms 55440 KB Output is correct
55 Correct 893 ms 55440 KB Output is correct
56 Correct 693 ms 55448 KB Output is correct
57 Correct 917 ms 55452 KB Output is correct
58 Execution timed out 1026 ms 55620 KB Time limit exceeded
59 Correct 814 ms 55660 KB Output is correct
60 Correct 704 ms 55692 KB Output is correct
61 Correct 689 ms 55664 KB Output is correct
62 Execution timed out 1020 ms 55700 KB Time limit exceeded
63 Execution timed out 1061 ms 55636 KB Time limit exceeded
64 Execution timed out 1002 ms 55660 KB Time limit exceeded
65 Correct 733 ms 55660 KB Output is correct
66 Execution timed out 1035 ms 55444 KB Time limit exceeded
67 Execution timed out 1044 ms 55444 KB Time limit exceeded
68 Execution timed out 1025 ms 55632 KB Time limit exceeded
69 Correct 916 ms 55692 KB Output is correct
70 Incorrect 436 ms 49860 KB Output isn't correct
71 Incorrect 686 ms 55660 KB Output isn't correct
72 Incorrect 786 ms 55656 KB Output isn't correct
73 Incorrect 791 ms 55660 KB Output isn't correct
74 Incorrect 687 ms 55656 KB Output isn't correct
75 Incorrect 659 ms 55888 KB Output isn't correct
76 Incorrect 643 ms 55448 KB Output isn't correct
77 Incorrect 911 ms 55660 KB Output isn't correct
78 Incorrect 927 ms 55664 KB Output isn't correct
79 Incorrect 493 ms 55656 KB Output isn't correct
80 Incorrect 325 ms 55684 KB Output isn't correct
81 Incorrect 497 ms 55660 KB Output isn't correct
82 Execution timed out 1024 ms 55660 KB Time limit exceeded
83 Incorrect 781 ms 55664 KB Output isn't correct
84 Incorrect 443 ms 55656 KB Output isn't correct
85 Incorrect 658 ms 55668 KB Output isn't correct
86 Incorrect 449 ms 55660 KB Output isn't correct
87 Incorrect 641 ms 55892 KB Output isn't correct
88 Incorrect 734 ms 55660 KB Output isn't correct
89 Correct 797 ms 55888 KB Output is correct
90 Incorrect 412 ms 50004 KB Output isn't correct
91 Incorrect 601 ms 55656 KB Output isn't correct
92 Incorrect 685 ms 55676 KB Output isn't correct
93 Incorrect 475 ms 55656 KB Output isn't correct
94 Incorrect 626 ms 55656 KB Output isn't correct
95 Incorrect 754 ms 55892 KB Output isn't correct
96 Incorrect 620 ms 55696 KB Output isn't correct
97 Incorrect 505 ms 55612 KB Output isn't correct
98 Incorrect 685 ms 55892 KB Output isn't correct
99 Incorrect 651 ms 55656 KB Output isn't correct
100 Incorrect 519 ms 55688 KB Output isn't correct