Submission #321487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321487	2020-11-12T12:51:05 Z	MetB	Sailing Race (CEOI12_race)	C++14	10 / 100	1362 ms	7356 KB

race

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 2000000;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int path[500][500][2], dp[500][500][2], dp_max[500][500][2];

int g[500][500], k;
int ans[500], n, m, nx[500][2];


void f_edge (int l, int r, int dir) {
	path[l][r][dir] = 1;
	dp[l][r][dir] = 1 + dp_max[r][nx[l][dir]][!dir];
}

void f (int l, int r, int dir) {
	for (int k = nx[l][dir]; k != r; k = nx[k][dir]) {
		path[l][r][dir] = max (dp[l][r][dir], path[l][k][dir] + path[k][r][dir]);
		dp[l][r][dir] = max (dp[l][r][dir], path[l][k][dir] + dp[k][r][dir]);
	}

	dp_max[l][r][dir] = max (dp[l][r][dir], dp_max[l][nx[r][!dir]][dir]);
}

int main () {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int x;
		while (cin >> x && x) {
			g[i][x-1] = 1;
		}

		nx[i][1] = (i + 1) % n;
		nx[i][0] = i ? i - 1 : n - 1;
	}

	for (int k = 1; k < n; k++)
		for (int i = 0; i < n; i++) {
			int l = i, r = (i + k) % n;
			dp[l][r][1] = path[l][r][1] = -1e9;
			dp[r][l][0] = path[r][l][0] = -1e9;
			if (g[l][r]) f_edge (l, r, 1);
			if (g[r][l]) f_edge (r, l, 0);
			f (l, r, 1);
			f (r, l, 0);
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int dir = 0; dir < 2; dir++)
				ans[i] = max (ans[i], dp[i][j][dir]);

	if (!k) {
		int ind = max_element(ans, ans + n) - ans;
		cout << ans[ind] << '\n' << ind + 1 << endl;
		return 0;
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int dir = 0; dir < 2; dir++) {
				int k = nx[j][dir];

				if (path[i][j][dir] <= 0) continue;

				while (k != i && !g[k][i]) k = nx[k][dir];

				if (k == i) continue;

				for (int l = nx[k][dir]; l != i; l = nx[l][dir]) {
					int ans_l = max(dp_max[l][nx[k][dir]][!dir], dp_max[l][nx[i][!dir]][dir]);
					if (g[j][l]) ans[k] = max (ans[k], 2 + path[i][j][dir] + ans_l);
					//cout << k << ' ' << i << ' ' << j << ' ' << l << ' ' << 2 + path[i][j][dir] + ans_l << endl;
				}

			}

	int ind = max_element(ans, ans + n) - ans;
	cout << ans[ind] << '\n' << ind + 1 << endl;
}

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Incorrect	1 ms	620 KB	Output isn't correct
3	Incorrect	1 ms	748 KB	Output isn't correct
4	Incorrect	1 ms	876 KB	Output isn't correct
5	Incorrect	2 ms	1004 KB	Output isn't correct
6	Incorrect	3 ms	1132 KB	Output isn't correct
7	Incorrect	3 ms	1260 KB	Output isn't correct
8	Incorrect	5 ms	1388 KB	Output isn't correct
9	Incorrect	5 ms	1516 KB	Output isn't correct
10	Correct	7 ms	1644 KB	Output is correct
11	Incorrect	6 ms	1644 KB	Output isn't correct
12	Incorrect	71 ms	3072 KB	Output isn't correct
13	Incorrect	203 ms	4460 KB	Output isn't correct
14	Incorrect	270 ms	5996 KB	Output isn't correct
15	Incorrect	1175 ms	7276 KB	Output isn't correct
16	Incorrect	1339 ms	7148 KB	Output isn't correct
17	Incorrect	1141 ms	7228 KB	Output isn't correct
18	Incorrect	565 ms	7276 KB	Output isn't correct
19	Incorrect	1362 ms	7276 KB	Output isn't correct
20	Incorrect	1272 ms	7356 KB	Output isn't correct