結果
問題 | No.992 最長増加部分列の数え上げ |
ユーザー |
![]() |
提出日時 | 2020-02-14 22:46:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 359 ms / 2,000 ms |
コード長 | 749 bytes |
コンパイル時間 | 286 ms |
コンパイル使用メモリ | 82,208 KB |
実行使用メモリ | 128,372 KB |
最終ジャッジ日時 | 2024-10-06 13:04:19 |
合計ジャッジ時間 | 11,763 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
# 解説を読みました# https://stackoverflow.com/questions/22923646/number-of-all-longest-increasing-subsequencesfrom bisect import bisect_leftmod = 10**9+7n = int(input())a = list(map(int, input().split()))row = [float("inf")]*ncumsum = [[0] for i in range(n)]nums = [[] for i in range(n)]for ai in a:i = bisect_left(row, ai)add = (row[i] == ai)row[i] = aiif i == 0:count = 1else:j = bisect_left(nums[i-1], -ai+1)count = cumsum[i-1][-1] - cumsum[i-1][j]if add:cumsum[i][-1] += countelse:cumsum[i].append(cumsum[i][-1]+count)nums[i].append(-ai)cumsum[i][-1] %= modi = bisect_left(row, float("inf"))ans = cumsum[i-1][-1]%modprint(ans)