結果

問題 No.1929 Exponential Sequence
コンテスト
ユーザー powell
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0