oj.uz

답안 #1042946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042946 2024-08-03T15:20:01 Z 42kangaroo 축구 경기장 (IOI23_soccer) C++17
6 / 100
 167 ms 35156 KB 
#include "soccer.h"
#include "bits/stdc++.h"


int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	using namespace std;
	using dp_t = vector<vector<vector<int>>>;
	bool allPos = true;
	int su = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			su += F[i][j];
		}
	}
	if (su == 1) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (F[i][j] == 1) {
					return N * N - min(i + 1, N - i) * min(j + 1, N - j);
				}
			}
		}
	} else {
		vector<pair<int, int>> ra(N);
		vector<int> les(N);
		for (int i = 0; i < N; ++i) {
			ra[i].first = 0;
			for (; ra[i].first < N; ra[i].first++) {
				if (F[i][ra[i].first] == 0) break;
			}
			ra[i].second = N - 1;
			for (; ra[i].second >= 0; ra[i].second--) {
				if (F[i][ra[i].second] == 0) break;
			}
			les[i] = ra[i].second - ra[i].first + 1;
			for (int j = ra[i].first; j <= ra[i].second; ++j) {
				if (F[i][j] == 1) allPos = false;
			}
			if (!allPos) break;
		}
		int tot = 0;
		int maI = max_element(les.begin(), les.end()) - les.begin();
		pair<int, int> actRa = ra[maI];
		pair<int, int> oRa = {maI, maI};
		tot = les[maI];
		while (allPos && oRa != make_pair(0, N - 1)) {
			int ne = oRa.first - 1;
			if (ne < 0 || (oRa.second < N - 1 && les[ne] < les[oRa.second + 1])) ne = oRa.second + 1;
			if (les[ne] < 0) break;
			if (actRa.first > ra[ne].first || actRa.second < ra[ne].second) allPos = false;
			actRa = ra[ne];
			tot += les[ne];
			oRa = {min(oRa.first, ne), max(oRa.second, ne)};
		}
		if (allPos) return tot;
		else if (N > 500) return 0;
		else {
			vector<vector<int>> prefS(N, vector<int>(N + 1, 0));
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					prefS[i][j + 1] = prefS[i][j] + F[i][j];
				}
			}
			dp_t dpU(N + 1, vector<vector<int>>(N + 1, vector<int>(N + 1, -N * N)));
			auto dpD = dpU;
			int ma = 0;
			for (int i = 0; i <= N; ++i) {
				for (int j = N - 1; j >= 0; --j) {
					for (int k = j + 1; k <= N; ++k) {
						if (i == 0)dpU[0][j][k] = 0;
						else if (prefS[i - 1][k] - prefS[i - 1][j] == 0) dpU[i][j][k] = dpU[i - 1][j][k] + k - j;
						else dpU[i][j][k] = max(dpU[i][j][k - 1], dpU[i][j + 1][k]);
					}
				}
			}
			for (int i = N; i >= 0; --i) {
				for (int j = N - 1; j >= 0; --j) {
					for (int k = j + 1; k <= N; ++k) {
						if (i == N) dpD[N][j][k] = 0;
						else if (prefS[i][k] - prefS[i][j] == 0) {
							dpD[i][j][k] = dpD[i + 1][j][k] + k - j;
							ma = max(ma, dpD[i][j][k] + dpU[i + 1][j][k] - k + j);
						}
						else dpD[i][j][k] = max(dpD[i][j][k - 1], dpD[i][j + 1][k]);
					}
				}
			}
			return ma;
		}
	}
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
   91 | }
      | ^

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 12 ms 2696 KB ok
9 Correct 167 ms 35156 KB ok

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 344 KB wrong
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 Incorrect 0 ms 344 KB wrong
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Incorrect 0 ms 344 KB wrong
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Incorrect 0 ms 344 KB wrong
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 12 ms 2696 KB ok
10 Correct 167 ms 35156 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Incorrect 0 ms 344 KB wrong
14 Halted 0 ms 0 KB -