結果

問題 No.209 Longest Mountain Subsequence
コンテスト
ユーザー rpy3cpp
提出日時 2015-05-17 18:51:19
言語 PyPy3
(7.3.15)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 643 bytes
コンパイル時間 295 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 76,996 KB
最終ジャッジ日時 2024-12-23 14:11:26
合計ジャッジ時間 2,166 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 6
権限があれば一括ダウンロードができます

ソースコード

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