結果
問題 | No.497 入れ子の箱 |
ユーザー | むらため |
提出日時 | 2019-02-04 23:44:30 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 225 ms / 5,000 ms |
コード長 | 1,428 bytes |
コンパイル時間 | 2,370 ms |
コンパイル使用メモリ | 70,976 KB |
実行使用メモリ | 23,180 KB |
最終ジャッジ日時 | 2023-09-14 03:30:03 |
合計ジャッジ時間 | 9,317 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 156 ms
20,388 KB |
testcase_04 | AC | 202 ms
20,524 KB |
testcase_05 | AC | 211 ms
19,256 KB |
testcase_06 | AC | 213 ms
20,992 KB |
testcase_07 | AC | 217 ms
20,200 KB |
testcase_08 | AC | 219 ms
20,884 KB |
testcase_09 | AC | 220 ms
23,180 KB |
testcase_10 | AC | 217 ms
19,392 KB |
testcase_11 | AC | 221 ms
21,932 KB |
testcase_12 | AC | 220 ms
12,076 KB |
testcase_13 | AC | 220 ms
11,856 KB |
testcase_14 | AC | 225 ms
11,988 KB |
testcase_15 | AC | 220 ms
12,452 KB |
testcase_16 | AC | 224 ms
12,472 KB |
testcase_17 | AC | 224 ms
12,592 KB |
testcase_18 | AC | 203 ms
21,436 KB |
testcase_19 | AC | 204 ms
21,688 KB |
testcase_20 | AC | 202 ms
21,476 KB |
testcase_21 | AC | 203 ms
21,484 KB |
testcase_22 | AC | 207 ms
21,576 KB |
testcase_23 | AC | 127 ms
4,380 KB |
testcase_24 | AC | 128 ms
4,376 KB |
testcase_25 | AC | 1 ms
4,380 KB |
testcase_26 | AC | 2 ms
4,376 KB |
testcase_27 | AC | 220 ms
19,120 KB |
testcase_28 | AC | 220 ms
18,904 KB |
testcase_29 | AC | 218 ms
18,780 KB |
testcase_30 | AC | 172 ms
4,380 KB |
testcase_31 | AC | 165 ms
4,376 KB |
ソースコード
import sequtils,algorithm template times*(n:int,body) = (for _ in 0..<n: body) template `max=`*(x,y) = x = max(x,y) template `min=`*(x,y) = x = min(x,y) proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': return result = 10 * result + k.ord - '0'.ord # 隣接リスト([n->[m1,m2,m3], ... ])を トポロジカルソート proc topologicalSort(E:seq[seq[int]],deleteIsolated:bool = false) : seq[int] = var visited = newSeq[int](E.len) var answer = newSeq[int]() proc visit(src:int) = visited[src] += 1 if visited[src] > 1: return for dst in E[src]: visit(dst) answer &= src # 葉から順に追加される for src in 0..<E.len: visit(src) if deleteIsolated: # 孤立点の除去 return answer.filterIt(visited[it] > 1 or E[it].len > 0) return answer let n = scan() let B = newSeqWith(n,(x:scan(),y:scan(),z:scan())) proc isSmall(a,b:tuple[x,y,z:int]): bool = var an = @[a.x,a.y,a.z].sorted(cmp) while true: if an[0] < b.x and an[1] < b.y and an[2] < b.z : return true if not an.nextPermutation() : return false var E = newSeqWith(n,newSeq[int]()) for i in 0..<n: for j in 0..<n: if isSmall(B[i],B[j]) : E[j] &= i var dp = newSeq[int](n) let TS = E.topologicalSort(true).reversed() for e in TS : for dst in E[e]: dp[dst] .max= dp[e] + 1 echo dp.max() + 1