結果

問題 No.137 貯金箱の焦り
ユーザー 👑 SPD_9X2
提出日時 2025-07-19 18:16:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 699 bytes
コンパイル時間 538 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 308,464 KB
最終ジャッジ日時 2025-07-19 18:16:51
合計ジャッジ時間 9,121 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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)
    mask = (2**(bit+1))-1
    for k in dp:
        if (k&mask) == (M&mask) and k <= M:
            ndp[k] = dp[k]
    dp = ndp

    # print (dp)

print (dp[M])
0