結果

問題 No.496 ワープクリスタル (給料日前編)
ユーザー lam6er
提出日時 2025-03-20 20:30:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,165 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 75,192 KB
最終ジャッジ日時 2025-03-20 20:32:07
合計ジャッジ時間 2,482 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

Gx, Gy, N, F = map(int, input().split())
crystals = [tuple(map(int, input().split())) for _ in range(N)]

INF = float('inf')
dp = [[INF] * (Gy + 1) for _ in range(Gx + 1)]
dp[0][0] = 0  # Initial position

for x, y, c in crystals:
    # Create a new DP table for the next state
    new_dp = [row[:] for row in dp]
    for a in range(Gx + 1):
        for b in range(Gy + 1):
            if dp[a][b] == INF:
                continue
            # Calculate new position after using this crystal
            new_a = min(a + x, Gx)
            new_b = min(b + y, Gy)
            # Update the new_dp with the minimum cost
            if new_dp[new_a][new_b] > dp[a][b] + c:
                new_dp[new_a][new_b] = dp[a][b] + c
    # Update dp to new_dp after processing this crystal
    dp = new_dp

# Calculate the minimum cost considering walking fees
min_cost = INF
for a in range(Gx + 1):
    for b in range(Gy + 1):
        if dp[a][b] != INF:
            walk_x = max(Gx - a, 0)
            walk_y = max(Gy - b, 0)
            total_cost = dp[a][b] + (walk_x + walk_y) * F
            if total_cost < min_cost:
                min_cost = total_cost

print(min_cost)
0