結果
問題 | No.1368 サイクルの中に眠る門松列 |
ユーザー |
![]() |
提出日時 | 2025-03-20 20:38:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 316 ms / 2,000 ms |
コード長 | 2,156 bytes |
コンパイル時間 | 161 ms |
コンパイル使用メモリ | 82,712 KB |
実行使用メモリ | 116,616 KB |
最終ジャッジ日時 | 2025-03-20 20:38:51 |
合計ジャッジ時間 | 2,967 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 15 |
ソースコード
import sys def are_distinct(x, y, z): return x != y and y != z and x != z def is_kadomatsu(x, y, z): if not are_distinct(x, y, z): return False return y == max(x, y, z) or y == min(x, y, z) def compute_linear(B): m = len(B) if m < 3: return 0 a = 0 # dp[i-3] b = 0 # dp[i-2] c = 0 # dp[i-1] for i in range(3, m + 1): x = B[i-3] y = B[i-2] z = B[i-1] valid = are_distinct(x, y, z) and ( (y > max(x, z)) or (y < min(x, z)) ) if valid: candidate = a + x else: candidate = 0 new_c = max(c, candidate) # Update the rolling variables a, b, c = b, c, new_c return c def solve(): input = sys.stdin.read().split() ptr = 0 T = int(input[ptr]) ptr += 1 for _ in range(T): N = int(input[ptr]) ptr += 1 A = list(map(int, input[ptr:ptr+N])) ptr += N linear_max = compute_linear(A) max_candidate = linear_max if N >= 3: # Check candidate 1: triplet (N-2, N-1, 0) x = A[-2] y = A[-1] z = A[0] valid1 = are_distinct(x, y, z) and ( (y > max(x, z)) or (y < min(x, z)) ) if valid1: start = 1 end = N - 3 if start <= end: subarray1 = A[start:end + 1] else: subarray1 = [] sum1 = x + compute_linear(subarray1) max_candidate = max(max_candidate, sum1) # Check candidate 2: triplet (N-1, 0, 1) x = A[-1] y = A[0] z = A[1] valid2 = are_distinct(x, y, z) and ( (y > max(x, z)) or (y < min(x, z)) ) if valid2: start = 2 end = N - 2 if start <= end: subarray2 = A[start:end + 1] else: subarray2 = [] sum2 = x + compute_linear(subarray2) max_candidate = max(max_candidate, sum2) print(max_candidate) solve()