結果
問題 | No.1929 Exponential Sequence |
ユーザー |
|
提出日時 | 2023-09-30 10:17:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 525 ms / 2,000 ms |
コード長 | 804 bytes |
コンパイル時間 | 263 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 124,868 KB |
最終ジャッジ日時 | 2024-07-23 04:23:11 |
合計ジャッジ時間 | 5,515 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 |
ソースコード
from bisect import bisect_right from itertools import product N, S = map(int, input().split()) A = list(map(int, input().split())) # 半分全列挙する left, right = A[:N // 2], A[N // 2:] # 左側を全列挙 left_all = [] for i, a in enumerate(left): tmp = [] x = a while x < S: tmp.append(x) x *= a left_all.append(tmp) # 左側の組合せをすべて作成 left_all_sorted = sorted(sum(comb) for comb in product(*left_all)) # 右側を全列挙 right_all = [] for i, a in enumerate(right): tmp = [] x = a while x < S: tmp.append(x) x *= a right_all.append(tmp) # 答えを得る ans = 0 for comb in product(*right_all): sum_right = sum(comb) ok = bisect_right(left_all_sorted, S - sum_right) ans += ok print(ans)