結果
問題 | No.1804 Intersection of LIS |
ユーザー |
|
提出日時 | 2022-01-11 22:53:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 419 ms / 2,000 ms |
コード長 | 631 bytes |
コンパイル時間 | 249 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 201,004 KB |
最終ジャッジ日時 | 2024-11-14 12:16:38 |
合計ジャッジ時間 | 9,883 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
import bisect n = int(input()) P = list(map(int,input().split())) inf = 10**10 min_lis = [inf]*(n+1) min_id = [] def lis(P): dp = [inf]*(n+1) id = [] for i,p in enumerate(P): ind = bisect.bisect_left(dp,p) dp[ind] = p id.append(ind) m = max(id) ans = [] for i in range(n)[::-1]: if id[i] == m: ans.append(P[i]) m -= 1 return ans[::-1] ans_min = lis(P) ans_max = lis([-p for p in P][::-1]) ans_max = [-p for p in ans_max][::-1] ans = [] for mi,ma in zip(ans_min,ans_max): if mi == ma: ans.append(mi) print(len(ans)) print(*ans)