結果

問題 No.137 貯金箱の焦り
ユーザー 👑 SPD_9X2
提出日時 2025-07-19 18:14:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 673 bytes
コンパイル時間 529 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 324,960 KB
最終ジャッジ日時 2025-07-19 18:14:24
合計ジャッジ時間 9,737 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

mod = 1234567891

N,M = map(int,input().split())
A = list(map(int,input().split()))

dp = defaultdict(int)
dp[0] = 1

for bit in range(60):

    nbit = 2**bit

    for i in range(N):

        add = (nbit * A[i])
        
        keys = list(dp.keys())
        keys.sort()
        keys.reverse()

        ndp = defaultdict(int)

        for k in keys:
            ndp[k] = (ndp[k] + dp[k]) % mod
            ndp[k+add] = (ndp[k+add] + dp[k]) % mod

        dp = ndp
        
    ndp = defaultdict(int)
    for k in dp:
        if k % nbit == M % nbit and k <= M:
            ndp[k] = dp[k]
    dp = ndp

    # print (dp)

print (dp[M])
0