oj.uz

답안 #1096845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096845 2024-10-05T09:25:14 Z vjudge1 Sailing Race (CEOI12_race) C++17
85 / 100
 3000 ms 4952 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 5 ms 2652 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 7 ms 2908 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 153 ms 2104 KB Output is correct
13 Correct 241 ms 2648 KB Output is correct
14 Correct 33 ms 3932 KB Output is correct
15 Correct 2909 ms 4444 KB Output is correct
16 Execution timed out 3053 ms 4700 KB Time limit exceeded
17 Correct 2875 ms 4664 KB Output is correct
18 Correct 43 ms 4440 KB Output is correct
19 Execution timed out 3073 ms 4700 KB Time limit exceeded
20 Execution timed out 3042 ms 4952 KB Time limit exceeded