oj.uz

답안 #524315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524315 2022-02-09T04:08:45 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 * m * n * n > 1e6) {
		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 * 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 39 ms 102468 KB Output is correct
2 Correct 39 ms 102528 KB Output is correct
3 Correct 61 ms 112604 KB Output is correct
4 Correct 56 ms 112504 KB Output is correct
5 Correct 49 ms 102512 KB Output is correct
6 Correct 43 ms 102540 KB Output is correct
7 Correct 38 ms 102628 KB Output is correct
8 Correct 44 ms 102884 KB Output is correct
9 Correct 46 ms 102944 KB Output is correct
10 Correct 41 ms 102788 KB Output is correct
11 Correct 47 ms 102976 KB Output is correct
12 Correct 40 ms 102852 KB Output is correct
13 Correct 40 ms 102804 KB Output is correct
14 Correct 42 ms 102876 KB Output is correct
15 Correct 45 ms 102852 KB Output is correct
16 Correct 57 ms 102940 KB Output is correct
17 Incorrect 39 ms 102792 KB Output isn't correct
18 Incorrect 39 ms 102680 KB Output isn't correct
19 Incorrect 47 ms 102876 KB Output isn't correct
20 Incorrect 38 ms 102852 KB Output isn't correct
21 Incorrect 52 ms 102724 KB Output isn't correct
22 Incorrect 50 ms 102788 KB Output isn't correct
23 Incorrect 37 ms 102892 KB Output isn't correct
24 Incorrect 48 ms 102852 KB Output isn't correct
25 Incorrect 38 ms 102868 KB Output isn't correct
26 Incorrect 37 ms 102852 KB Output isn't correct
27 Execution timed out 1083 ms 111816 KB Time limit exceeded
28 Incorrect 47 ms 104080 KB Output isn't correct
29 Incorrect 43 ms 104480 KB Output isn't correct
30 Incorrect 47 ms 104924 KB Output isn't correct
31 Execution timed out 1088 ms 112972 KB Time limit exceeded
32 Incorrect 48 ms 104628 KB Output isn't correct
33 Execution timed out 1090 ms 116704 KB Time limit exceeded
34 Incorrect 47 ms 104184 KB Output isn't correct
35 Execution timed out 1086 ms 116676 KB Time limit exceeded
36 Execution timed out 1094 ms 116676 KB Time limit exceeded
37 Correct 69 ms 102980 KB Output is correct
38 Runtime error 173 ms 131076 KB Execution killed with signal 9
39 Correct 52 ms 102996 KB Output is correct
40 Runtime error 183 ms 131076 KB Execution killed with signal 9
41 Correct 55 ms 102956 KB Output is correct
42 Incorrect 44 ms 102860 KB Output isn't correct
43 Runtime error 171 ms 131076 KB Execution killed with signal 9
44 Execution timed out 1091 ms 116676 KB Time limit exceeded
45 Runtime error 175 ms 131076 KB Execution killed with signal 9
46 Runtime error 176 ms 131076 KB Execution killed with signal 9
47 Runtime error 175 ms 131076 KB Execution killed with signal 9
48 Runtime error 183 ms 131072 KB Execution killed with signal 9
49 Runtime error 168 ms 131076 KB Execution killed with signal 9
50 Runtime error 170 ms 131076 KB Execution killed with signal 9
51 Runtime error 168 ms 131076 KB Execution killed with signal 9
52 Runtime error 175 ms 131076 KB Execution killed with signal 9
53 Runtime error 166 ms 131076 KB Execution killed with signal 9
54 Runtime error 169 ms 131072 KB Execution killed with signal 9
55 Runtime error 176 ms 131076 KB Execution killed with signal 9
56 Runtime error 163 ms 131076 KB Execution killed with signal 9
57 Runtime error 166 ms 131076 KB Execution killed with signal 9
58 Runtime error 178 ms 131076 KB Execution killed with signal 9
59 Runtime error 165 ms 131076 KB Execution killed with signal 9
60 Runtime error 167 ms 131076 KB Execution killed with signal 9
61 Runtime error 182 ms 131076 KB Execution killed with signal 9
62 Runtime error 170 ms 131076 KB Execution killed with signal 9
63 Runtime error 165 ms 131076 KB Execution killed with signal 9
64 Runtime error 162 ms 131076 KB Execution killed with signal 9
65 Runtime error 166 ms 131076 KB Execution killed with signal 9
66 Runtime error 172 ms 131076 KB Execution killed with signal 9
67 Runtime error 167 ms 131076 KB Execution killed with signal 9
68 Runtime error 176 ms 131076 KB Execution killed with signal 9
69 Runtime error 167 ms 131076 KB Execution killed with signal 9
70 Incorrect 97 ms 122396 KB Output isn't correct
71 Runtime error 168 ms 131076 KB Execution killed with signal 9
72 Runtime error 164 ms 131076 KB Execution killed with signal 9
73 Runtime error 166 ms 131076 KB Execution killed with signal 9
74 Runtime error 165 ms 131076 KB Execution killed with signal 9
75 Runtime error 167 ms 131076 KB Execution killed with signal 9
76 Runtime error 162 ms 131076 KB Execution killed with signal 9
77 Runtime error 165 ms 131076 KB Execution killed with signal 9
78 Runtime error 180 ms 131076 KB Execution killed with signal 9
79 Runtime error 172 ms 131076 KB Execution killed with signal 9
80 Runtime error 170 ms 131076 KB Execution killed with signal 9
81 Runtime error 171 ms 131076 KB Execution killed with signal 9
82 Runtime error 198 ms 131076 KB Execution killed with signal 9
83 Runtime error 166 ms 131076 KB Execution killed with signal 9
84 Runtime error 162 ms 131076 KB Execution killed with signal 9
85 Runtime error 175 ms 131076 KB Execution killed with signal 9
86 Runtime error 165 ms 131076 KB Execution killed with signal 9
87 Runtime error 166 ms 131076 KB Execution killed with signal 9
88 Runtime error 175 ms 131076 KB Execution killed with signal 9
89 Runtime error 167 ms 131076 KB Execution killed with signal 9
90 Incorrect 96 ms 122404 KB Output isn't correct
91 Runtime error 173 ms 131076 KB Execution killed with signal 9
92 Runtime error 168 ms 131076 KB Execution killed with signal 9
93 Runtime error 169 ms 131076 KB Execution killed with signal 9
94 Runtime error 171 ms 131076 KB Execution killed with signal 9
95 Runtime error 177 ms 131076 KB Execution killed with signal 9
96 Runtime error 165 ms 131076 KB Execution killed with signal 9
97 Runtime error 173 ms 131076 KB Execution killed with signal 9
98 Runtime error 166 ms 131076 KB Execution killed with signal 9
99 Runtime error 168 ms 131076 KB Execution killed with signal 9
100 Runtime error 167 ms 131076 KB Execution killed with signal 9