結果
問題 | No.15 カタログショッピング |
ユーザー | Mao-beta |
提出日時 | 2024-02-29 02:21:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 533 ms / 5,000 ms |
コード長 | 1,745 bytes |
コンパイル時間 | 958 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 122,176 KB |
最終ジャッジ日時 | 2024-02-29 02:21:59 |
合計ジャッジ時間 | 4,486 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 46 ms
57,832 KB |
testcase_01 | AC | 50 ms
57,832 KB |
testcase_02 | AC | 47 ms
57,832 KB |
testcase_03 | AC | 56 ms
65,884 KB |
testcase_04 | AC | 46 ms
57,832 KB |
testcase_05 | AC | 511 ms
122,048 KB |
testcase_06 | AC | 517 ms
122,048 KB |
testcase_07 | AC | 530 ms
122,176 KB |
testcase_08 | AC | 533 ms
122,176 KB |
testcase_09 | AC | 518 ms
122,176 KB |
ソースコード
import sys import math import bisect from heapq import heapify, heappop, heappush from collections import deque, defaultdict, Counter from functools import lru_cache from itertools import accumulate, combinations, permutations, product sys.setrecursionlimit(1000000) MOD = 10 ** 9 + 7 MOD99 = 998244353 input = lambda: sys.stdin.readline().strip() NI = lambda: int(input()) NMI = lambda: map(int, input().split()) NLI = lambda: list(NMI()) SI = lambda: input() SMI = lambda: input().split() SLI = lambda: list(SMI()) EI = lambda m: [NLI() for _ in range(m)] def split_and_list(A): """ 半分全列挙して前半と後半の部分和を返す O(2^(N//2)) """ N = len(A) former, latter = A[:N // 2], A[N // 2:] fn, ln = len(former), len(latter) F = [] for k in range(fn + 1): F += [[sum(former[cc] for cc in c), tuple(cc+1 for cc in c)] for c in combinations(range(fn), k)] L = [] for k in range(ln + 1): L += [[sum(latter[cc] for cc in c), tuple(cc+fn+1 for cc in c)] for c in combinations(range(ln), k)] return F, L def main(): N, S = NMI() P = [NI() for _ in range(N)] F, L = split_and_list(P) F.sort() L.sort() FX = [] FI = [] LX = [] LI = [] for x, i in F: FX.append(x) FI.append(i) for x, i in L: LX.append(x) LI.append(i) ans = [] for fx, fi in zip(FX, FI): if fx > S: continue lx = S - fx bl = bisect.bisect_left(LX, lx) br = bisect.bisect_right(LX, lx) for bi in range(bl, br): ans.append(sorted(list(fi) + list(LI[bi]))) ans.sort() for row in ans: print(*row) if __name__ == "__main__": main()