結果
問題 | No.15 カタログショッピング |
ユーザー | 6soukiti29 |
提出日時 | 2017-07-26 12:05:20 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 257 ms / 5,000 ms |
コード長 | 1,652 bytes |
コンパイル時間 | 5,471 ms |
コンパイル使用メモリ | 74,952 KB |
実行使用メモリ | 43,248 KB |
最終ジャッジ日時 | 2023-09-12 13:33:15 |
合計ジャッジ時間 | 6,410 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 251 ms
41,960 KB |
testcase_06 | AC | 254 ms
42,168 KB |
testcase_07 | AC | 255 ms
42,420 KB |
testcase_08 | AC | 257 ms
43,248 KB |
testcase_09 | AC | 246 ms
41,796 KB |
ソースコード
import sequtils,strutils,algorithm proc `<`(x,y : seq[int]):bool = # seq[int]をsortするのに必要 for i in 0..min(x.len,y.len): if x[i] < y[i]: return true elif x[i] == y[i]: continue else: return false if x.len < y.len: return true else: return false type kumi = tuple[ku : seq[int],s : int] var N,S : int (N,S) = stdin.readline.split.map(parseInt) var P = newSeq[int](N) p : int ans = newSeq[kumi](0) for n in 0..<N: p = stdin.readline.parseInt P[n] = p if N == 1: if P[0] == S: echo S else: var A = P[0..<(N div 2)] B = P[(N div 2)..<N] Ka : seq[kumi] Ka2 = Ka Kb : seq[kumi] Kb2 = Kb kk : kumi kk = (@[],0) Ka = @[kk] Kb = @[kk] for i,a in A: Ka2 = @[] for k in Ka: Ka2.add((k.ku & @[i + 1] ,k.s + a)) Ka &= Ka2 for i,b in B: Kb2 = @[] for k in Kb: Kb2.add((k.ku & @[i + (N div 2) + 1] ,k.s + b)) Kb &= Kb2 Ka = Ka.sortedByIt(it.s) Kb = Kb.sortedByIt(it.s) Kb.reverse var p = 0 p2 = 0 for i in 0..Ka.high: while p <= Kb.high: if Ka[i].s + Kb[p].s == S: ans.add((Ka[i].ku & Kb[p].ku, Ka[i].s + Kb[p].s)) p += 1 p2 += 1 elif Ka[i].s + Kb[p].s > S: p += 1 elif Ka[i].s + Kb[p].s < S: break p -= p2 p2 = 0 ans = ans.sortedByIt(it.ku) for s in ans: echo s.ku.join(" ")