Submission #55213

# Submission time Handle Problem Language Result Execution time Memory
55213 2018-07-06T11:01:24 Z linkret Sailing Race (CEOI12_race) C++14
40 / 100
1031 ms 5220 KB
#include <bits/stdc++.h>

using namespace std;

const int maxn = 505, inf = 1e9;

int n, id;
vector<int> adj[maxn];
vector<int> radj[maxn];

bool between(int l, int r, int i) {
	if(l > r) {
		return i >= l || i <= r;
	} else {
		return i >= l && i <= r;
	}
}

int dp[2][2][maxn][maxn];

int main() {
	ios_base::sync_with_stdio(false);

	cin >> n >> id;

	for(int i = 0, j; i < n; i++) {
		while(true) {
			cin >> j;
			if(!j) break;
			j--;
			adj[i].push_back(j);
			radj[j].push_back(i);
		}
	}

	for(int i = 0; i < n; i++) {
		sort(adj[i].begin(), adj[i].end());

		for(int j = 0; j < n; j++) {
			
		}
	}

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			dp[1][0][i][j] = -inf;
			dp[1][1][i][j] = -inf;
		}
	}

	for(int i = 0; i < n; i++) {
		dp[1][0][i][i] = 0;
		dp[1][1][i][i] = 0;
	}

	for(int len = 1; len < n; len++) {
		for(int i = 0; i < n; i++) {
			int j = (i + len) % n;
			
			for(int k : radj[j]) {
				if(between(i, j, k)) {
					dp[1][0][i][j] = max(dp[1][0][i][j], 1 + dp[1][0][i][k]);
				}
			}

			for(int k : radj[i]) {
				if(between(i, j, k)) {
					dp[1][1][i][j] = max(dp[1][1][i][j], 1 + dp[1][1][k][j]);
				}
			}

			for(int k : adj[i]) {
				if(between(i, j, k)) {
					dp[0][0][i][j] = max(dp[0][0][i][j], 1 + max(dp[0][1][(i + 1) % n][k], dp[0][0][k][j]));
				}
			}

			for(int k : adj[j]) {
				if(between(i, j, k)) {
					dp[0][1][i][j] = max(dp[0][1][i][j], 1 + max(dp[0][1][i][k], dp[0][0][k][(j - 1 + n) % n]));
				}
			}
		}
	}

	int mxm = 0, t = 0;

	for(int i = 0; i < n; i++) {
		int tmp = dp[0][0][i][(i - 1 + n) % n];
		if(tmp > mxm) {
			mxm = tmp;
			t = i;
		}
	}

	cout << mxm << endl << t + 1 << endl;

	// for(int i = 0; i < n; i++) {
	// 	for(int j = 0; j < n; j++) {
	// 		int k = dp[0][1][i][j];
	// 		if(k < 0)
	// 			cout << 'x' << " ";
	// 		else
	// 			cout << k << " ";
	// 	}
	// 	cout << endl;
	// }

	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Incorrect 3 ms 616 KB Output isn't correct
3 Incorrect 4 ms 692 KB Output isn't correct
4 Incorrect 3 ms 820 KB Output isn't correct
5 Correct 3 ms 896 KB Output is correct
6 Incorrect 4 ms 1044 KB Output isn't correct
7 Correct 7 ms 1172 KB Output is correct
8 Incorrect 5 ms 1280 KB Output isn't correct
9 Correct 10 ms 1452 KB Output is correct
10 Correct 27 ms 1656 KB Output is correct
11 Correct 18 ms 1656 KB Output is correct
12 Incorrect 39 ms 2408 KB Output isn't correct
13 Incorrect 74 ms 3044 KB Output isn't correct
14 Correct 124 ms 4068 KB Output is correct
15 Incorrect 348 ms 4956 KB Output isn't correct
16 Incorrect 613 ms 5164 KB Output isn't correct
17 Incorrect 688 ms 5164 KB Output isn't correct
18 Correct 223 ms 5164 KB Output is correct
19 Incorrect 1031 ms 5220 KB Output isn't correct
20 Incorrect 877 ms 5220 KB Output isn't correct