結果

問題 No.1929 Exponential Sequence
ユーザー lam6er
提出日時 2025-03-26 15:49:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 393 ms / 2,000 ms
コード長 885 bytes
コンパイル時間 273 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 186,660 KB
最終ジャッジ日時 2025-03-26 15:50:17
合計ジャッジ時間 4,487 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n, S = map(int, input().split())
a = list(map(int, input().split()))

def generate_sums(half):
    sums = [0]
    for num in half:
        exponents = []
        current = num
        while True:
            exponents.append(current)
            next_p = current * num
            if next_p > S:
                break
            current = next_p
        new_sums = []
        for s in sums:
            for e in exponents:
                new_sum = s + e
                new_sums.append(new_sum)
        sums = new_sums
    return sums

mid = n // 2
first_half = a[:mid]
second_half = a[mid:]

sum1 = generate_sums(first_half)
sum2 = generate_sums(second_half)

sum2.sort()

total = 0
for s in sum1:
    if s > S:
        continue
    remaining = S - s
    if remaining < 0:
        continue
    cnt = bisect.bisect_right(sum2, remaining)
    total += cnt

print(total)
0