結果

問題 No.1929 Exponential Sequence
ユーザー lam6er
提出日時 2025-03-31 17:31:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 145 ms / 2,000 ms
コード長 1,685 bytes
コンパイル時間 128 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 84,784 KB
最終ジャッジ日時 2025-03-31 17:32:10
合計ジャッジ時間 2,683 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict
import bisect

def generate_group_sums(group, max_s):
    sum_counts = defaultdict(int)
    sum_counts[0] = 1  # Initial state: sum is 0 with 1 way (no elements selected)
    for a in group:
        temp = defaultdict(int)
        for sum_so_far in sum_counts:
            current_count = sum_counts[sum_so_far]
            k = 1
            while True:
                try:
                    power = a ** k
                except OverflowError:
                    break
                new_sum = sum_so_far + power
                if new_sum > max_s:
                    break
                temp[new_sum] += current_count
                k += 1
        sum_counts = temp
    return sum_counts

def main():
    n, S = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    half = n // 2
    group1 = a[:half]
    group2 = a[half:]
    
    sum_counts1 = generate_group_sums(group1, S)
    sum_counts2 = generate_group_sums(group2, S)
    
    # Process group2 for binary search
    sorted_s2 = sorted(sum_counts2.items())
    s2_list = []
    prefix_counts = []
    current_total = 0
    for s, cnt in sorted_s2:
        s2_list.append(s)
        current_total += cnt
        prefix_counts.append(current_total)
    
    total = 0
    for s1, cnt1 in sum_counts1.items():
        remaining = S - s1
        if remaining < 0:
            continue
        # Find the largest index where s2 <= remaining
        idx = bisect.bisect_right(s2_list, remaining) - 1
        if idx >= 0:
            total += cnt1 * prefix_counts[idx]
    
    print(total)

if __name__ == "__main__":
    main()
0