Submission #1096895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096895		vjudge1	Sailing Race (CEOI12_race)	C++17	100 / 100	582 ms	5140 KiB

race

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, dp1[2][505][505], dp2[2][505][505], ans1, ans2 = 1;
vector<int> vec[505], rvec[505];
int next(int x, int y) { return ((x + y - 1) % n + n) % n + 1; }
int min(int x, int y) { return x < y ? x : y; }
int max(int x, int y) { return x > y ? x : y; }
bool bemiddle(int l, int m, int r) { return l < r && l < m && m < r || l > r && (l < m || m < r); }
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1, x; i <= n; ++i)
		while (true)
		{
			scanf("%d", &x);
			if (x == 0)
				break;
			vec[i].push_back(x);
			rvec[x].push_back(i);
		}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j < i; ++j)
			for (int k = 0; k < 2; ++k)
				dp2[k][i][j] = dp2[k][j][i] = -1e9;
		sort(rvec[i].begin(), rvec[i].end());
	}
	for (int len = 2; len <= n; ++len)
		for (int i = 1; i <= n; ++i)
		{
			int j = next(i, len - 1);
			for (int k : vec[i])
				if (i < j && i <= k && k <= j || i > j && (k >= i || k <= j))
				{
					dp1[0][i][j] = max(dp1[0][i][j], max(dp1[1][next(i, 1)][k], dp1[0][k][j]) + 1);
					dp2[0][i][j] = max(dp2[0][i][j], dp2[0][k][j] + 1);
				}
			for (int k : vec[j])
				if (i < j && i <= k && k <= j || i > j && (k >= i || k <= j))
				{
					dp1[1][i][j] = max(dp1[1][i][j], max(dp1[1][i][k], dp1[0][k][next(j, -1)]) + 1);
					dp2[1][i][j] = max(dp2[1][i][j], dp2[1][i][k] + 1);
				}
		}
	for (int i = 1; i <= n; ++i)
	{
		int x = max(dp1[0][i][next(i, -1)], dp1[1][next(i, 1)][i]);
		if (x > ans1)
		{
			ans1 = x;
			ans2 = i;
		}
	}
	if (k == 1)
		for (int j = 1; j <= n; ++j)
			for (int k = 1; k <= n; ++k)
				for (int l : vec[k])
				{
					vector<int>::iterator it = lower_bound(rvec[j].begin(), rvec[j].end(), k);
					if (bemiddle(j, l, k) && it != rvec[j].begin()) // j - l - i - k
						if (bemiddle(l, *(--it), k))
						{
							int x = 1 + dp2[1][k][j] + 1 + max(dp1[1][next(j, 1)][l], dp1[0][l][next(*it, -1)]);
							if (x > ans1)
							{
								ans1 = x;
								ans2 = *it;
							}
						}
					it = upper_bound(rvec[j].begin(), rvec[j].end(), k);
					if (bemiddle(k, l, j) && it != rvec[j].end() && bemiddle(k, *it, l)) // k - i - l - j
					{
						int x = 1 + dp2[0][j][k] + 1 + max(dp1[1][next(*it, 1)][l], dp1[0][l][next(j, -1)]);
						if (x > ans1)
						{
							ans1 = x;
							ans2 = *it;
						}
					}
					// for (int i : rvec[j])
					// 	if (i < j && i < k && k < j || i > j && (k > i || k < j))
					// 	{
					// 		if (j < i && j < l && l < i || j > i && (l > j || l < i)) // j - l - i - k
					// 		{
					// 			int x = 1 + dp2[1][k][j] + 1 + max(dp1[1][next(j, 1)][l], dp1[0][l][next(i, -1)]);
					// 			if (x > ans1)
					// 			{
					// 				ans1 = x;
					// 				ans2 = i;
					// 			}
					// 		}
					// 	}
					// 	else if (k != i && k != j)
					// 	{
					// 		if (i < j && i < l && l < j || i > j && (l > i || l < j)) // k - i - l - j
					// 		{
					// 			int x = 1 + dp2[0][j][k] + 1 + max(dp1[1][next(i, 1)][l], dp1[0][l][next(j, -1)]);
					// 			if (x > ans1)
					// 			{
					// 				ans1 = x;
					// 				ans2 = i;
					// 			}
					// 		}
					// 	}
				}
	printf("%d\n%d\n", ans1, ans2);
	return 0;
}

Compilation message (stderr)

race.cpp: In function 'bool bemiddle(int, int, int)':
race.cpp:10:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   10 | bool bemiddle(int l, int m, int r) { return l < r && l < m && m < r || l > r && (l < m || m < r); }
      |                                             ~~~~~~~~~~~~~~~^~~~~~~~
race.cpp: In function 'int main()':
race.cpp:35:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |     if (i < j && i <= k && k <= j || i > j && (k >= i || k <= j))
      |         ~~~~~~~~~~~~~~~~^~~~~~~~~
race.cpp:41:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   41 |     if (i < j && i <= k && k <= j || i > j && (k >= i || k <= j))
      |         ~~~~~~~~~~~~~~~~^~~~~~~~~
race.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
race.cpp:17:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100