結果
問題 | No.497 入れ子の箱 |
ユーザー |
![]() |
提出日時 | 2023-07-11 12:43:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 152 ms / 5,000 ms |
コード長 | 997 bytes |
コンパイル時間 | 431 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 77,656 KB |
最終ジャッジ日時 | 2024-09-13 03:20:10 |
合計ジャッジ時間 | 5,472 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
import sysinput = sys.stdin.readlinefrom bisect import *from copy import *def compress(lst):"""B: lstを座圧したリストD: indexから元の値を取得する辞書"""B = []D = dict()vals = deepcopy(lst)vals = list(set(vals))vals.sort()for i in range(len(lst)):ind = bisect_left(vals, lst[i])B.append(ind)for i in range(len(B)):D[lst[i]] = B[i]return B, D, valsN = int(input())H, W, D = [0] * N, [0] * N, [0] * Nfor i in range(N):H[i], W[i], D[i] = sorted(map(int, input().split()))H, _, _ = compress(H)W, _, _ = compress(W)D, _, _ = compress(D)A = []for i in range(N):A.append((H[i], W[i], D[i]))A.sort()dp = [1] * Ndef check(a, b):flag = 1for i in range(3):if A[a][i] >= A[b][i]:return Falsereturn Truefor i in range(1, N):for j in range(i):if check(j, i):dp[i] = max(dp[i], dp[j] + 1)print(max(dp))