Submission #1096845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096845		vjudge1	Sailing Race (CEOI12_race)	C++17	85 / 100	3073 ms	4952 KiB

race

#include <stdio.h>
#include <vector>
using namespace std;
int n, k, dp1[2][505][505], dp2[2][505][505], ans1, ans2 = 1;
vector<int> vec[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; }
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);
		}
	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;
	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 i = 1; i <= n; ++i)
			for (auto j : vec[i])
				for (int k = 1; k <= n; ++k)
					if (i < j && i < k && k < j || i > j && (k > i || k < j))
					{
						for (int l : vec[k])
							if (j < i && j < l && l < i || j > i && (l > j || l < i))
							{
								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)
					{
						for (int l : vec[k])
							if (i < j && i < l && l < j || i > j && (l > 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 'int main()':
race.cpp:29:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   29 |     if (i < j && i <= k && k <= j || i > j && (k >= i || k <= j))
      |         ~~~~~~~~~~~~~~~~^~~~~~~~~
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:54:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   54 |      if (i < j && i < k && k < j || i > j && (k > i || k < j))
      |          ~~~~~~~~~~~~~~~^~~~~~~~
race.cpp:57:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   57 |        if (j < i && j < l && l < i || j > i && (l > j || l < i))
      |            ~~~~~~~~~~~~~~~^~~~~~~~
race.cpp:70:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   70 |        if (i < j && i < l && l < j || i > j && (l > i || l < j))
      |            ~~~~~~~~~~~~~~~^~~~~~~~
race.cpp:50:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   50 |  if (k == 1)
      |     ^
race.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
race.cpp:15:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

• Subtask 1: 85 / 100