답안 #1083406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1083406	2024-09-03T05:27:37 Z	ef10	Sailing Race (CEOI12_race)	C++17	10 / 100	505 ms	8788 KB

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Incorrect	0 ms	604 KB	Output isn't correct
3	Incorrect	1 ms	604 KB	Output isn't correct
4	Incorrect	1 ms	716 KB	Output isn't correct
5	Incorrect	1 ms	860 KB	Output isn't correct
6	Incorrect	2 ms	860 KB	Output isn't correct
7	Incorrect	2 ms	1116 KB	Output isn't correct
8	Incorrect	3 ms	1116 KB	Output isn't correct
9	Incorrect	4 ms	1368 KB	Output isn't correct
10	Correct	4 ms	1624 KB	Output is correct
11	Incorrect	5 ms	1372 KB	Output isn't correct
12	Incorrect	31 ms	3332 KB	Output isn't correct
13	Incorrect	107 ms	5208 KB	Output isn't correct
14	Incorrect	241 ms	6684 KB	Output isn't correct
15	Incorrect	425 ms	8428 KB	Output isn't correct
16	Incorrect	420 ms	8788 KB	Output isn't correct
17	Incorrect	421 ms	8788 KB	Output isn't correct
18	Incorrect	505 ms	8408 KB	Output isn't correct
19	Incorrect	429 ms	8528 KB	Output isn't correct
20	Incorrect	417 ms	8532 KB	Output isn't correct