oj.uz

답안 #524319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524319 2022-02-09T04:12:07 Z boykut Bomb (IZhO17_bomb) C++14
19 / 100
 1000 ms 131076 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2555;
int arr[N][N], brr[N][N];
int pref[N][N];
int t[N][N* 4], lazy[N][4 * N];

void push(int X, int v, int vl, int vr) {
	if (vl == vr || lazy[X][v] == -1) return;
	lazy[X][v << 1] = lazy[X][v];
	lazy[X][v << 1 | 1] = lazy[X][v];
	int vm = vl + vr >> 1;
	t[X][v << 1] = lazy[X][v] * (vm - vl + 1);
	t[X][v << 1 | 1] = lazy[X][v] * (vr - vm);
	lazy[X][v] = -1;
}
void update(int X, int l, int r, int x, int v, int vl, int vr) {
	push(X, v, vl, vr);
	if (l > vr || vl > r) return;
	if (l <= vl && vr <= r) {
		t[X][v] = x * (vr - vl + 1);
		lazy[X][v] = x;
		return;
	}
	int vm = vl + vr >> 1;
	update(X, l, r, x, v << 1, vl, vm);
	update(X, l, r, x, v << 1 | 1, vm + 1, vr);
	t[X][v] = t[X][v << 1] + t[X][v << 1 | 1];
}
void update(int X, int l, int r, int x) {
	update(X, l, r, x, 1, 0, N - 1);
}
int query(int X, int i, int v, int vl, int vr) {
	push(X, v, vl, vr);
	if (vl == vr)
		return t[X][v];
	int vm = vl + vr >> 1, q;
	if (i <= vm)
		q = query(X, i, v << 1, vl, vm);
	else
		q = query(X, i, v << 1 | 1, vm + 1, vr);
	t[X][v] = t[X][v << 1] + t[X][v << 1 | 1];
	return q;
}
int query(int X, int i) {
	return query(X, i, 1, 0, N - 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < 4 * N; j++)
			lazy[i][j] = -1;

	int n, m;
	cin >> n >> m;

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char x; cin >> x;
			arr[i][j] = x - '0';
			if (arr[i][j])
				cnt++;
		}
	}
	if (!cnt) {
		cout << 0 << '\n';
		return 0;
	}

	if (n * n * n * m * 12 > 1e8) {
		int a = 0, b = 0;
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 1) cnt++;
				else {
					if (cnt)
						a = min(a, cnt);
					cnt = 0;
				}
			}
			if (cnt)
				a = min(a, cnt);
		}
		for (int j = 0; j < m; j++) {
			int cnt = 0;
			for (int i = 0; i < n; i++) {
				if (arr[i][j] == 1) cnt++;
				else {
					if (cnt)
						b = min(b, cnt);
					cnt = 0;
				}
			}
			if (cnt)
				b = min(b, cnt);
		}
		cout << a * 1ll * b << '\n';
		return 0;
	}

	if (n > m) {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				brr[i][j] = arr[j][i];
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				arr[i][j] = brr[i][j];
			}
		}
		swap(n, m);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			update(i, j, j, arr[i][j]);
			pref[i][j] = arr[i][j];
			pref[i][j] += (i ? pref[i - 1][j] : 0);
			pref[i][j] += (j ? pref[i][j - 1] : 0);
			pref[i][j] -= (i && j ? pref[i - 1][j - 1] : 0);
		}
	}

	auto get = [&](int a, int b, int c, int d) ->int {
		int s = pref[c][d];
		s -= (a ? pref[a - 1][d] : 0);
		s -= (b ? pref[c][b - 1] : 0);
		s += (a && b ? pref[a - 1][b - 1] : 0);
		return s;
	};

	// brute force

	int Q = 2;
	auto check = [&](int a, int b) ->int {
		for (int i = 0; i + a - 1 < n; i++) {
			for (int j = 0; j + b - 1 < m; j++) {
				int g = get(i, j, i + a - 1, j + b - 1);
				if (g == a * b) {
					for (int x = i; x <= i + a - 1; x++) {
						update(x, j, j + b - 1, Q);
					}
				}
			}
		}
		int ok = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (query(i, j) != 0 && query(i, j) != Q)
					ok = 0;
			}
		}
		Q++;
		return ok;
	};

	//O(n*n * 12*m * 12*12)
	//O(10000 *120 * 144)
	//O(1000000)

	int ans = 0;
	for (int a = 1; a <= n; a++) {
		int l = 1, r = m;
		while (l < r) {
			int b = (l + r + 1) / 2;
			if (check(a, b))
				l = b;
			else
				r = b - 1;
		}
		if (check(a, l))
			ans = max(ans, a * l);
	}
	cout << ans << '\n';

	return 0;
}

Compilation message

bomb.cpp: In function 'void push(int, int, int, int)':
bomb.cpp:14:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |  int vm = vl + vr >> 1;
      |           ~~~^~~~
bomb.cpp: In function 'void update(int, int, int, int, int, int, int)':
bomb.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int vm = vl + vr >> 1;
      |           ~~~^~~~
bomb.cpp: In function 'int query(int, int, int, int, int)':
bomb.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int vm = vl + vr >> 1, q;
      |           ~~~^~~~

Subtask #1
19.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 102468 KB Output is correct
2 Correct 40 ms 102604 KB Output is correct
3 Correct 57 ms 112556 KB Output is correct
4 Correct 58 ms 112624 KB Output is correct
5 Correct 51 ms 102572 KB Output is correct
6 Correct 45 ms 102476 KB Output is correct
7 Correct 39 ms 102604 KB Output is correct
8 Correct 54 ms 102936 KB Output is correct
9 Correct 45 ms 102864 KB Output is correct
10 Correct 41 ms 102852 KB Output is correct
11 Correct 44 ms 102980 KB Output is correct
12 Correct 42 ms 102820 KB Output is correct
13 Correct 40 ms 102776 KB Output is correct
14 Correct 52 ms 102848 KB Output is correct
15 Correct 44 ms 102880 KB Output is correct
16 Correct 61 ms 103004 KB Output is correct
17 Incorrect 40 ms 102796 KB Output isn't correct
18 Incorrect 39 ms 102724 KB Output isn't correct
19 Incorrect 40 ms 102860 KB Output isn't correct
20 Incorrect 40 ms 102836 KB Output isn't correct
21 Incorrect 40 ms 102748 KB Output isn't correct
22 Incorrect 40 ms 102748 KB Output isn't correct
23 Incorrect 40 ms 102948 KB Output isn't correct
24 Incorrect 40 ms 102780 KB Output isn't correct
25 Incorrect 45 ms 102828 KB Output isn't correct
26 Incorrect 44 ms 102852 KB Output isn't correct
27 Incorrect 43 ms 103984 KB Output isn't correct
28 Incorrect 48 ms 104080 KB Output isn't correct
29 Incorrect 42 ms 104572 KB Output isn't correct
30 Execution timed out 1091 ms 116000 KB Time limit exceeded
31 Execution timed out 1100 ms 112964 KB Time limit exceeded
32 Incorrect 48 ms 104740 KB Output isn't correct
33 Execution timed out 1097 ms 116660 KB Time limit exceeded
34 Incorrect 41 ms 104268 KB Output isn't correct
35 Execution timed out 1101 ms 116728 KB Time limit exceeded
36 Execution timed out 1099 ms 116764 KB Time limit exceeded
37 Correct 49 ms 102980 KB Output is correct
38 Incorrect 135 ms 131072 KB Output isn't correct
39 Correct 48 ms 102988 KB Output is correct
40 Runtime error 164 ms 131076 KB Execution killed with signal 9
41 Correct 50 ms 102980 KB Output is correct
42 Incorrect 40 ms 102932 KB Output isn't correct
43 Incorrect 129 ms 131072 KB Output isn't correct
44 Execution timed out 1097 ms 116652 KB Time limit exceeded
45 Incorrect 124 ms 131072 KB Output isn't correct
46 Incorrect 125 ms 131072 KB Output isn't correct
47 Incorrect 128 ms 131072 KB Output isn't correct
48 Incorrect 133 ms 131072 KB Output isn't correct
49 Incorrect 124 ms 131072 KB Output isn't correct
50 Incorrect 126 ms 131072 KB Output isn't correct
51 Incorrect 124 ms 131072 KB Output isn't correct
52 Incorrect 127 ms 131072 KB Output isn't correct
53 Incorrect 126 ms 131072 KB Output isn't correct
54 Incorrect 132 ms 131072 KB Output isn't correct
55 Incorrect 124 ms 131072 KB Output isn't correct
56 Incorrect 135 ms 131072 KB Output isn't correct
57 Incorrect 132 ms 131072 KB Output isn't correct
58 Incorrect 129 ms 131072 KB Output isn't correct
59 Incorrect 124 ms 131072 KB Output isn't correct
60 Incorrect 126 ms 131072 KB Output isn't correct
61 Incorrect 124 ms 131072 KB Output isn't correct
62 Incorrect 127 ms 131072 KB Output isn't correct
63 Incorrect 124 ms 131072 KB Output isn't correct
64 Incorrect 125 ms 131072 KB Output isn't correct
65 Incorrect 126 ms 131072 KB Output isn't correct
66 Incorrect 130 ms 131072 KB Output isn't correct
67 Incorrect 122 ms 131008 KB Output isn't correct
68 Incorrect 130 ms 131072 KB Output isn't correct
69 Incorrect 123 ms 130928 KB Output isn't correct
70 Incorrect 100 ms 122572 KB Output isn't correct
71 Incorrect 132 ms 130912 KB Output isn't correct
72 Incorrect 127 ms 130928 KB Output isn't correct
73 Incorrect 127 ms 130776 KB Output isn't correct
74 Incorrect 123 ms 130788 KB Output isn't correct
75 Incorrect 124 ms 130756 KB Output isn't correct
76 Incorrect 125 ms 130716 KB Output isn't correct
77 Incorrect 125 ms 130644 KB Output isn't correct
78 Incorrect 135 ms 130768 KB Output isn't correct
79 Incorrect 138 ms 130616 KB Output isn't correct
80 Incorrect 125 ms 130640 KB Output isn't correct
81 Incorrect 125 ms 130428 KB Output isn't correct
82 Incorrect 131 ms 130496 KB Output isn't correct
83 Incorrect 124 ms 130448 KB Output isn't correct
84 Incorrect 122 ms 130452 KB Output isn't correct
85 Incorrect 122 ms 130396 KB Output isn't correct
86 Incorrect 123 ms 130368 KB Output isn't correct
87 Incorrect 124 ms 130384 KB Output isn't correct
88 Incorrect 123 ms 130492 KB Output isn't correct
89 Incorrect 123 ms 130244 KB Output isn't correct
90 Incorrect 94 ms 122504 KB Output isn't correct
91 Incorrect 131 ms 130372 KB Output isn't correct
92 Incorrect 125 ms 130156 KB Output isn't correct
93 Incorrect 122 ms 130356 KB Output isn't correct
94 Incorrect 149 ms 129988 KB Output isn't correct
95 Incorrect 128 ms 130168 KB Output isn't correct
96 Incorrect 123 ms 130100 KB Output isn't correct
97 Incorrect 123 ms 129836 KB Output isn't correct
98 Incorrect 122 ms 129908 KB Output isn't correct
99 Incorrect 133 ms 130096 KB Output isn't correct
100 Incorrect 125 ms 129884 KB Output isn't correct