結果

問題 No.209 Longest Mountain Subsequence
ユーザー rpy3cpprpy3cpp
提出日時 2015-05-17 18:51:19
言語 PyPy3
(7.3.15)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 643 bytes
コンパイル時間 461 ms
コンパイル使用メモリ 87,188 KB
実行使用メモリ 78,140 KB
最終ジャッジ日時 2023-08-25 02:08:34
合計ジャッジ時間 2,539 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 MLE -
testcase_02 MLE -
testcase_03 MLE -
testcase_04 MLE -
testcase_05 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def LMS(ps):
  L = LIM(ps)
  R = LIM(ps[::-1])
  return max(i + d for i, d in zip(L, R[::-1])) - 1

def LIM(ps):
  n = len(ps)
  dp = [[0] * (i+1) for i in range(n)]
  for k in range(n):
    psk = ps[k]
    dpk = dp[k]
    for j in range(k):
      psj = ps[j]
      if psk > psj:
        dpj = dp[j]
        low = 2 * psj - psk
        dpkj = 2
        for psi, dpji in zip(ps, dpj):
          if dpji >= dpkj and psi > low and psj > psi:
            dpkj = dpji + 1
        dpk[j] = dpkj
    dpk[k] = 1
  return list(map(max, dp))

T = int(input())
for t in range(T):
  N = int(input())
  ps = list(map(int, input().split()))
  print(LMS(ps))
0