Submission #1083406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083406		ef10	Sailing Race (CEOI12_race)	C++17	10 / 100	505 ms	8788 KiB

race

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define MAXN 505

int N,K;
vector<int> adj[MAXN];
LL dp[MAXN][MAXN][2];
LL mdp[MAXN][MAXN][2];

int calc(int s, int l, bool cc) {
	if (cc) {
		return (s+l) % N;
	}
	int ret = s - l;
	if (ret < 0) {
		ret += N;
	}
	return ret;
}

int len(int s, int e, bool cc) {
	int ret = e - s;
	if (ret < 0) {
		ret += N;
	}
	if (cc) {
		return ret;
	}
	return N-ret;
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		while (a!=0) {
			a--;
			adj[i].push_back(a);
			cin >> a;
		}
	}
	for (int i = 0; i < N; i++) {
		for (auto n : adj[i]) {
			dp[i][n][0] = 1;
			dp[i][n][1] = 1;
		}
	}
	for (int d = 0; d < 2; d++) {
		for (int l = 1; l < N; l++) {
			for (int i = 0; i < N; i++) {
				int e = calc(i,l,d);
				for (int k = 1; k < l; k++) {
					int m = calc(i,k,d);
					if (dp[i][m][d] && dp[m][e][d]) {
						dp[i][e][d] = max(dp[i][e][d],dp[i][m][d] + dp[m][e][d]);
					}
				}
				mdp[i][e][d] = max(mdp[i][e-1][d],dp[i][e][d]);
			}
		}
	}
	LL res = 0;
	int st = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < 2; k++) {
			if (mdp[i][calc(i,N-1,k)][k] > res) {
				res = mdp[i][calc(i,N-1,k)][k];
				st = i+1;
			}
		}
	}
	if (K == 0) {
		cout << res << endl << st << endl;
		return 0;
	}
	for (int i = 0; i < N; i++) {
		for (auto n : adj[i]) {
			for (int k = 0; k < 2; k++) {
				int l = len(n,i,k); l++;
				for (; l < N; l++) {
					int e = calc(n,l,k);
					if (dp[n][e][k]) {
						int li = len(e,i,!k);li--;
						if (li>0) {
							LL current = 1+dp[n][e][k]+mdp[e][calc(e,li,!k)][!k];
							if (current > res) {
								res = current;
								st = i+1;
							}
						}
					}
				}
			}
		}
	}
	cout << res << endl << st << endl;
}

• Subtask 1: 10 / 100