結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
53,120 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | AC | 128 ms
111,104 KB |
testcase_06 | AC | 128 ms
111,360 KB |
testcase_07 | AC | 80 ms
107,520 KB |
testcase_08 | AC | 155 ms
111,104 KB |
testcase_09 | WA | - |
testcase_10 | AC | 156 ms
109,440 KB |
testcase_11 | AC | 158 ms
109,184 KB |
testcase_12 | AC | 137 ms
109,440 KB |
testcase_13 | AC | 120 ms
108,928 KB |
testcase_14 | WA | - |
testcase_15 | AC | 121 ms
109,312 KB |
ソースコード
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]))