結果

問題 No.1368 サイクルの中に眠る門松列
コンテスト
ユーザー flippergo
提出日時 2024-10-02 13:08:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,364 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 111,360 KB
最終ジャッジ日時 2024-10-02 13:08:41
合計ジャッジ時間 3,641 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    A = A+A
    a,b,c = A[0:3]
    if a!=b and b!=c and c!=a and (max(a,b,c)==b or min(a,b,c)==b):
        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
        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]])
    else:
        dp0 = [0]
    a,b,c = A[1:4]
    if a!=b and b!=c and c!=a and (max(a,b,c)==b or min(a,b,c)==b):
        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
        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]])
    else:
        dp1 = [0]
    a,b,c = A[2:5]
    if a!=b and b!=c and c!=a and (max(a,b,c)==b or min(a,b,c)==b):
        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
        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]])
    else:
        dp2 = [0]
    print(max(dp0[-1],dp1[-1],dp2[-1]))
0