結果

問題 No.1782 ManyCoins
ユーザー tamatotamato
提出日時 2021-12-12 19:03:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,190 ms / 2,000 ms
コード長 987 bytes
コンパイル時間 498 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 113,536 KB
最終ジャッジ日時 2024-07-21 06:39:30
合計ジャッジ時間 13,979 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

mod = 1000000007
eps = 10**-9
inf = 10 ** 18
def main():
import sys
from collections import deque
input = sys.stdin.readline
N, L = map(int, input().split())
W = list(map(int, input().split()))
W.sort()
w_max = W[-1]
seen = [inf] * w_max
que = deque([(0, 0)])
seen[0] = 0
while que:
v, d = que.popleft()
if d != seen[v]:
continue
for w in W[:-1]:
u = v + w
if u < w_max:
if d < seen[u]:
seen[u] = d
que.appendleft((u, d))
else:
u -= w_max
if d + 1 < seen[u]:
seen[u] = d + 1
que.append((u, d + 1))
ans = 0
for i in range(w_max):
add = L // w_max
if i:
if L % w_max >= i:
add += 1
add -= seen[i]
ans += max(0, add)
print(ans)
if __name__ == '__main__':
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0