結果

問題 No.1368 サイクルの中に眠る門松列
ユーザー flippergoflippergo
提出日時 2024-10-02 12:41:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,166 bytes
コンパイル時間 518 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 111,360 KB
最終ジャッジ日時 2024-10-02 12:41:09
合計ジャッジ時間 4,276 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    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
    flag0 = 0 in K0
    if M0==0 or (not flag0):
        dp0 = [0]
    if M0>=1 and flag0:
        dp0[0] = A[K0[0]]
    if M0>=2 and flag0:
        if K0[1]>=K0[0]+3:
            dp0[1] = dp0[0]+A[K0[1]]
        else:
            dp0[1] = dp0[0]
    if M0>=3 and flag0:
        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]])
    if flag0:
        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
    flag1 = 1 in K1
    if M1==0 or (not flag1):
        dp1 = [0]
    if M1>=1 and flag1:
        dp1[0] = A[K1[0]]
    if M1>=2 and flag1:
        if K1[1]>=K1[0]+3:
            dp1[1] = dp1[0]+A[K1[1]]
        else:
            dp1[1] = dp1[0]
    if M1>=3 and flag1:
        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]])
    if flag1:
        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
    flag2 = 2 in K2
    if M2==0 or (not flag2):
        dp2 = [0]
    if M2>=1 and flag2:
        dp2[0] = A[K2[0]]
    if M2>=2 and flag2:
        if K2[1]>=K2[0]+3:
            dp2[1] = dp2[0]+A[K2[1]]
        else:
            dp2[1] = dp2[0]
    if M2>=3 and flag2:
        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]])
    if flag2:
        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