結果

問題 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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 10 WA * 5
権限があれば一括ダウンロードができます

ソースコード

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]))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0