結果

問題 No.1368 サイクルの中に眠る門松列
ユーザー flippergoflippergo
提出日時 2024-10-02 08:11:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,821 bytes
コンパイル時間 798 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 111,232 KB
最終ジャッジ日時 2024-10-02 08:11:23
合計ジャッジ時間 5,592 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,480 KB
testcase_01 AC 43 ms
52,864 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 161 ms
111,104 KB
testcase_06 AC 161 ms
111,104 KB
testcase_07 AC 111 ms
110,848 KB
testcase_08 AC 173 ms
111,232 KB
testcase_09 WA -
testcase_10 AC 208 ms
109,440 KB
testcase_11 AC 239 ms
109,568 KB
testcase_12 AC 209 ms
109,184 KB
testcase_13 AC 211 ms
109,184 KB
testcase_14 WA -
testcase_15 AC 206 ms
109,184 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    A = A+A
    K0 = []
    for i in range(N-3+1):
        a,b,c = A[i:i+3]
        if a!=b and b!=c and c!=a and (max(a,b,c)==b or min(a,b,c)==b):
            K0.append(i)
    M0 = len(K0)
    dp0 = [0]*M0
    if M0==0:
        dp0 = [0]
    if M0>=1:
        dp0[0] = A[K0[0]]
    if M0>=2:
        if K0[1]>=K0[0]+3:
            dp0[1] = dp0[0]+A[K0[1]]
        else:
            dp0[1] = dp0[0]
    if M0>=3:
        if K0[2]>=K0[1]+3:
            dp0[2] = dp0[1]+A[K0[2]]
        else:
            dp0[2] = dp0[1]
            if K0[2]>=K0[0]+3:
                dp0[2] = max(dp0[2],dp0[0]+A[K0[2]])
    for j in range(3,M0):
        if K0[j]>=K0[j-1]+3:
            dp0[j] = dp0[j-1]+A[K0[j]]
        else:
            dp0[j] = dp0[j-1]
            if K0[j]>=K0[j-2]+3:
                dp0[j] = max(dp0[j],dp0[j-2]+A[K0[j]])
            else:
                dp0[j] = max(dp0[j],dp0[j-3]+A[K0[j]])
    K1 = []
    for i in range(1,N-2+1):
        a,b,c = A[i:i+3]
        if a!=b and b!=c and c!=a and (max(a,b,c)==b or min(a,b,c)==b):
            K1.append(i)
    M1 = len(K1)
    dp1 = [0]*M1
    if M1==0:
        dp1 = [0]
    if M1>=1:
        dp1[0] = A[K1[0]]
    if M1>=2:
        if K1[1]>=K1[0]+3:
            dp1[1] = dp1[0]+A[K1[1]]
        else:
            dp1[1] = dp1[0]
    if M1>=3:
        if K1[2]>=K1[1]+3:
            dp1[2] = dp1[1]+A[K1[2]]
        else:
            dp1[2] = dp1[1]
            if K1[2]>=K1[0]+3:
                dp1[2] = max(dp1[2],dp1[0]+A[K1[2]])
    for j in range(3,M1):
        if K1[j]>=K1[j-1]+3:
            dp1[j] = dp1[j-1]+A[K1[j]]
        else:
            dp1[j] = dp1[j-1]
            if K1[j]>=K1[j-2]+3:
                dp1[j] = max(dp1[j],dp1[j-2]+A[K1[j]])
            else:
                dp1[j] = max(dp1[j],dp1[j-3]+A[K1[j]])
    K2 = []
    for i in range(2,N-1+1):
        a,b,c = A[i:i+3]
        if a!=b and b!=c and c!=a and (max(a,b,c)==b or min(a,b,c)==b):
            K2.append(i)
    M2 = len(K2)
    dp2 = [0]*M2
    if M2==0:
        dp2 = [0]
    if M2>=1:
        dp2[0] = A[K2[0]]
    if M2>=2:
        if K2[1]>=K2[0]+3:
            dp2[1] = dp2[0]+A[K2[1]]
        else:
            dp2[1] = dp2[0]
    if M2>=3:
        if K2[2]>=K2[1]+3:
            dp2[2] = dp2[1]+A[K2[2]]
        else:
            dp2[2] = dp2[1]
            if K2[2]>=K2[0]+3:
                dp2[2] = max(dp2[2],dp2[0]+A[K2[2]])
    for j in range(3,M2):
        if K2[j]>=K2[j-1]+3:
            dp2[j] = dp2[j-1]+A[K2[j]]
        else:
            dp2[j] = dp2[j-1]
            if K2[j]>=K2[j-2]+3:
                dp2[j] = max(dp2[j],dp2[j-2]+A[K2[j]])
            else:
                dp2[j] = max(dp2[j],dp2[j-3]+A[K2[j]])
    print(max(dp0[-1],dp1[-1],dp2[-1]))
0