結果

問題 No.992 最長増加部分列の数え上げ
コンテスト
ユーザー brthyyjp
提出日時 2020-02-15 08:02:01
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 714 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 848,908 KB
最終ジャッジ日時 2024-10-06 13:43:30
合計ジャッジ時間 3,076 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 MLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
l = list(map(int, input().split()))

MOD = 10**9+7

import bisect

dp0 = [float('inf')]*(n+1)
dp0[0] = -float('inf')
# dp[i]: 長さiの増加部分列の末尾の要素の最小値（できないときはfloat('inf')

dp1 = [[float('inf')]*(n+1) for j in range(n+1)]
for i in range(n+1):
    dp1[i][0] = -float('inf')

cnt = [0]*(n+1)
cnt[0] = 1
M = 0

dp2 = [[0]*(n+1) for _ in range(n+1)]
dp2[0][1] = 1

for i in range(n):
  a = l[i]
  x = bisect.bisect_left(dp0, a)
  dp0[x] = min(dp0[x], a)
  cnt[x] += 1
  M = max(x, M)
  dp1[x][cnt[x]] = -a
  y = bisect.bisect(dp1[x-1], -a)-1
  dp2[x][cnt[x]] += dp2[x][cnt[x]-1]+dp2[x-1][cnt[x-1]]-dp2[x-1][y]

#print(dp2)
#print(M)
print(dp2[M][cnt[M]])
0