結果

問題 No.10 ＋か×か
コンテスト
ユーザー tktk_snsn
提出日時 2021-10-26 23:42:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 909 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 278,548 KB
最終ジャッジ日時 2024-10-06 07:34:18
合計ジャッジ時間 8,926 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 1 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
import heapq
inf = 10 ** 18
N = int(input())
total = int(input())
A = list(map(int, input().split()))

dist = defaultdict(lambda: inf)
prev = defaultdict(lambda: -1)
dist[(A[0], 1)] = 0
que = [(0, A[0], 1)]    # cost, total, index
while que:
    ds, s, i = heapq.heappop(que)
    if dist[s] < s:
        continue
    if i == N:
        if s == total:
            break
        continue

    t = s + A[i]
    if t <= total and dist[(t, i + 1)] > ds:
        heapq.heappush(que, (ds, t, i + 1))
        prev[(t, i + 1)] = s
    t = s * A[i]
    if t <= total and dist[(t, i + 1)] > ds + (1 << i):
        heapq.heappush(que, (ds + (1 << i), t, i + 1))
        prev[(t, i + 1)] = s

ans = []
for i in range(N - 1):
    s = prev[(total, N - i)]
    if s + A[N - 1 - i] == total:
        ans.append("+")
    else:
        ans.append("*")
    total = s

print("".join(ans[::-1]))
0