結果

問題 No.1368 サイクルの中に眠る門松列
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0