oj.uz

Submission #1083406

# Submission time Handle Problem Language Result Execution time Memory
1083406 2024-09-03T05:27:37 Z ef10 Sailing Race (CEOI12_race) C++17
10 / 100
 505 ms 8788 KB 
// 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

# Verdict Execution time Memory 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