oj.uz

Submission #1017490

# Submission time Handle Problem Language Result Execution time Memory
1017490 2024-07-09T08:22:30 Z pavement Soccer Stadium (IOI23_soccer) C++17
54 / 100
 4500 ms 181088 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define eb emplace_back

using ll = long long;
using ii = pair<int, int>;
using iiii = tuple<int, int, int, int>;

int clr[2005][2005], clu[2005][2005], cld[2005][2005];
ii clrp[2005][2005], clrs[2005][2005], par[4000005];
ll ans, dp[4000005];

vector<iiii> get_maximal_rects(const int &N, const vector<vector<int> > &F) {
	vector<iiii> cur_rects;
	for (int i = 0; i < N; i++) {
		for (int j = N - 1; j >= 0; j--) {
			if (F[i][j] == 1) {
				clr[i][j] = j;
			} else if (j + 1 < N) {
				clr[i][j] = clr[i][j + 1];
			} else {
				clr[i][j] = N;
			}
			if (F[i][j] == 1) {
				clu[i][j] = i;
			} else if (i > 0) {
				clu[i][j] = clu[i - 1][j];
			} else {
				clu[i][j] = -1;
			}
			if (F[i][j] == 1) {
				clrp[i][j] = mp(N, N);
			} else if (i > 0) {
				clrp[i][j] = min(clrp[i - 1][j], mp(clr[i][j], i));
			} else {
				clrp[i][j] = mp(clr[i][j], i);
			}
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			if (F[i][j] == 1) {
				cld[i][j] = i;
			} else if (i + 1 < N) {
				cld[i][j] = cld[i + 1][j];
			} else {
				cld[i][j] = N;
			}
			if (F[i][j] == 1) {
				clrs[i][j] = mp(N, N);
			} else if (i + 1 < N) {
				clrs[i][j] = min(clrs[i + 1][j], mp(clr[i][j], i));
			} else {
				clrs[i][j] = mp(clr[i][j], i);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (F[i][j] == 1 || (j != 0 && F[i][j - 1] == 0)) {
				continue;
			}
			int l1 = clu[i][j] + 1;
			int r1 = cld[i][j] - 1;
			int nj = j;
			while (l1 <= r1) {
				if (F[l1][nj] == 1 || cld[l1][nj] <= r1) {
					break;
				}
				int b1, g1;
				if (clu[l1][nj] + 1 == l1) {
					tie(b1, g1) = clrp[r1][nj];
				} else {
					tie(b1, g1) = clrs[l1][nj];
				}
				cur_rects.eb(l1, j, r1, b1 - 1);
				// obstacle at (g1, b1)
				if (b1 == N) {
					break;
				}
				if (i < g1) {
					r1 = g1 - 1;
				} else if (i > g1) {
					l1 = g1 + 1;
				} else {
					break;
				}
				nj = b1;
			}
		}
	}
	return cur_rects;
}

vector<vector<int> > rotate(const int &N, const vector<vector<int> > &F) {
	vector<vector<int> > G(N, vector<int>(N, 0));
	for (int col = N - 1; col >= 0; col--) {
		for (int row = 0; row < N; row++) {
			G[row][col] = F[N - col - 1][row];
		}
	}
	return G;
}

ii unpack(const int &N, const int &x) {
	int r = x / N, c = x % N;
	return mp(r, c);
}

int biggest_stadium(int N, vector<vector<int> > F) {
	vector<iiii> all_rects;
	vector<vector<int> > H(N, vector<int>(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			H[i][j] = i * N + j;
		}
	}
	for (int rep = 0; rep < 2; rep++) {
		auto cur_rects = get_maximal_rects(N, F);
		for (auto [r1, c1, r2, c2] : cur_rects) {
			auto [nr1, nc1] = unpack(N, H[r1][c1]);
			auto [nr2, nc2] = unpack(N, H[r2][c2]);
			all_rects.eb(min(nr1, nr2), min(nc1, nc2), max(nr1, nr2), max(nc1, nc2));
		}
		F = rotate(N, F);
		H = rotate(N, H);
	}
	sort(all_rects.begin(), all_rects.end(), [](const auto &lhs, const auto &rhs) {
		auto [r11, c11, r12, c12] = lhs;
		auto [r21, c21, r22, c22] = rhs;
		return c12 - c11 > c22 - c21;
	});
	all_rects.erase(unique(all_rects.begin(), all_rects.end()), all_rects.end());
	for (int i = 0; i < (int)all_rects.size(); i++) {
		auto [r11, c11, r12, c12] = all_rects[i];
		for (int j = 0; j < i; j++) {
			auto [r21, c21, r22, c22] = all_rects[j];
			if (c21 <= c11 && c12 <= c22 && r11 <= r21 && r22 <= r12) {
				dp[i] = max(dp[i], dp[j] + (ll)((c22 - c21 + 1) - (c12 - c11 + 1)) * (r22 - r21 + 1));
			}
		}
		ans = max(ans, dp[i] + (ll)(r12 - r11 + 1) * (c12 - c11 + 1));
	}
	return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 856 KB ok
4 Correct 1 ms 600 KB ok
5 Correct 0 ms 448 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 2 ms 2908 KB ok
8 Correct 26 ms 21816 KB ok
9 Correct 415 ms 181088 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 440 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 440 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 604 KB ok
16 Correct 0 ms 604 KB ok
17 Correct 0 ms 604 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 1 ms 604 KB ok
24 Correct 1 ms 440 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 0 ms 604 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 856 KB ok
5 Correct 1 ms 600 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 440 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 604 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 1 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 1 ms 604 KB ok
26 Correct 1 ms 440 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 1116 KB ok
31 Correct 1 ms 1116 KB ok
32 Correct 1 ms 1368 KB ok
33 Correct 1 ms 1112 KB ok
34 Correct 1 ms 1112 KB ok
35 Correct 1 ms 1116 KB ok
36 Correct 1 ms 1116 KB ok
37 Correct 1 ms 956 KB ok
38 Correct 1 ms 860 KB ok
39 Correct 1 ms 1116 KB ok
40 Correct 1 ms 860 KB ok
41 Correct 2 ms 1116 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 856 KB ok
5 Correct 1 ms 600 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 440 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 604 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 1 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 1 ms 604 KB ok
26 Correct 1 ms 440 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 1116 KB ok
31 Correct 1 ms 1116 KB ok
32 Correct 1 ms 1368 KB ok
33 Correct 1 ms 1112 KB ok
34 Correct 1 ms 1112 KB ok
35 Correct 1 ms 1116 KB ok
36 Correct 1 ms 1116 KB ok
37 Correct 1 ms 956 KB ok
38 Correct 1 ms 860 KB ok
39 Correct 1 ms 1116 KB ok
40 Correct 1 ms 860 KB ok
41 Correct 2 ms 1116 KB ok
42 Execution timed out 4508 ms 25092 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 856 KB ok
5 Correct 1 ms 600 KB ok
6 Correct 0 ms 448 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 2 ms 2908 KB ok
9 Correct 26 ms 21816 KB ok
10 Correct 415 ms 181088 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 440 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 1 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 344 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 0 ms 604 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 1 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 604 KB ok
31 Correct 1 ms 440 KB ok
32 Correct 0 ms 604 KB ok
33 Correct 0 ms 604 KB ok
34 Correct 0 ms 604 KB ok
35 Correct 1 ms 1116 KB ok
36 Correct 1 ms 1116 KB ok
37 Correct 1 ms 1368 KB ok
38 Correct 1 ms 1112 KB ok
39 Correct 1 ms 1112 KB ok
40 Correct 1 ms 1116 KB ok
41 Correct 1 ms 1116 KB ok
42 Correct 1 ms 956 KB ok
43 Correct 1 ms 860 KB ok
44 Correct 1 ms 1116 KB ok
45 Correct 1 ms 860 KB ok
46 Correct 2 ms 1116 KB ok
47 Execution timed out 4508 ms 25092 KB Time limit exceeded
48 Halted 0 ms 0 KB -