結果

問題 No.1929 Exponential Sequence
ユーザー powellpowell
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
54,472 KB
testcase_01 AC 38 ms
53,668 KB
testcase_02 AC 37 ms
52,876 KB
testcase_03 AC 505 ms
124,640 KB
testcase_04 AC 38 ms
53,212 KB
testcase_05 AC 38 ms
53,556 KB
testcase_06 AC 37 ms
52,928 KB
testcase_07 AC 37 ms
54,008 KB
testcase_08 AC 37 ms
52,464 KB
testcase_09 AC 37 ms
53,212 KB
testcase_10 AC 37 ms
52,840 KB
testcase_11 AC 37 ms
53,696 KB
testcase_12 AC 38 ms
52,884 KB
testcase_13 AC 38 ms
52,808 KB
testcase_14 AC 38 ms
52,724 KB
testcase_15 AC 60 ms
69,976 KB
testcase_16 AC 46 ms
60,628 KB
testcase_17 AC 38 ms
53,076 KB
testcase_18 AC 39 ms
52,948 KB
testcase_19 AC 36 ms
53,208 KB
testcase_20 AC 37 ms
54,016 KB
testcase_21 AC 507 ms
124,676 KB
testcase_22 AC 380 ms
102,856 KB
testcase_23 AC 518 ms
124,868 KB
testcase_24 AC 280 ms
92,212 KB
testcase_25 AC 525 ms
124,620 KB
testcase_26 AC 487 ms
124,400 KB
testcase_27 AC 37 ms
53,492 KB
権限があれば一括ダウンロードができます

ソースコード

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