Submission #321489

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321489	2020-11-12T12:55:05 Z	MetB	Sailing Race (CEOI12_race)	C++14	100 / 100	1285 ms	7276 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 (path[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][0] = (i + 1) % n;
		nx[i][1] = 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][0] = path[l][r][0] = -1e9;
			dp[r][l][1] = path[r][l][1] = -1e9;
			if (g[l][r]) f_edge (l, r, 0);
			if (g[r][l]) f_edge (r, l, 1);
			f (l, r, 0);
			f (r, l, 1);
		}

	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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	640 KB	Output is correct
2	Correct	1 ms	620 KB	Output is correct
3	Correct	1 ms	748 KB	Output is correct
4	Correct	1 ms	876 KB	Output is correct
5	Correct	2 ms	1004 KB	Output is correct
6	Correct	3 ms	1132 KB	Output is correct
7	Correct	3 ms	1260 KB	Output is correct
8	Correct	5 ms	1388 KB	Output is correct
9	Correct	5 ms	1516 KB	Output is correct
10	Correct	7 ms	1644 KB	Output is correct
11	Correct	6 ms	1644 KB	Output is correct
12	Correct	77 ms	3052 KB	Output is correct
13	Correct	209 ms	4460 KB	Output is correct
14	Correct	274 ms	5868 KB	Output is correct
15	Correct	1165 ms	7276 KB	Output is correct
16	Correct	1222 ms	7228 KB	Output is correct
17	Correct	1150 ms	7148 KB	Output is correct
18	Correct	579 ms	7276 KB	Output is correct
19	Correct	1285 ms	7276 KB	Output is correct
20	Correct	1269 ms	7276 KB	Output is correct