oj.uz

답안 #1017184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017184 2024-07-09T05:42:27 Z pavement 축구 경기장 (IOI23_soccer) C++17
14 / 100
 1457 ms 2097152 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;
			while (l1 <= r1) {
				int b1, g1;
				if (clu[l1][j] + 1 == l1) {
					tie(b1, g1) = clrp[r1][j];
				} else {
					tie(b1, g1) = clrs[l1][j];
				}
				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;
				}
			}
		}
	}
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 440 KB ok
7 Correct 2 ms 2908 KB ok
8 Correct 24 ms 21864 KB ok
9 Correct 364 ms 181264 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 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 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 440 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 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Runtime error 1457 ms 2097152 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 440 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 0 ms 348 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Runtime error 1457 ms 2097152 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 440 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 0 ms 348 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Runtime error 1457 ms 2097152 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 440 KB ok
8 Correct 2 ms 2908 KB ok
9 Correct 24 ms 21864 KB ok
10 Correct 364 ms 181264 KB ok
11 Correct 1 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 440 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 0 ms 348 KB ok
19 Correct 0 ms 344 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Runtime error 1457 ms 2097152 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -