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

race

#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;
}

Subtask #1

40.0 / 100.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