結果

問題 No.2366 登校
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:01:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,189 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 82,752 KB
実行使用メモリ 79,744 KB
最終ジャッジ日時 2025-06-12 15:01:38
合計ジャッジ時間 2,292 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    K = int(input[idx]); idx +=1
    T_val = int(input[idx]); idx +=1

    squares = []
    for _ in range(K):
        A = int(input[idx])-1; idx +=1
        B = int(input[idx])-1; idx +=1
        C = int(input[idx]); idx +=1
        D = int(input[idx]); idx +=1
        squares.append((A, B, C, D))

    S = (N-1) + (M-1)
    if S <= T_val:
        print(0)
        return

    required = S - T_val

    # Compute d1 (distance from (0,0) to all cells)
    d1 = [[-1]*M for _ in range(N)]
    q = deque()
    q.append((0,0))
    d1[0][0] = 0
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]
    while q:
        i, j = q.popleft()
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < N and 0 <= nj < M and d1[ni][nj] == -1:
                d1[ni][nj] = d1[i][j] + 1
                q.append((ni, nj))

    # Compute d2 (distance from (N-1, M-1) to all cells)
    d2 = [[-1]*M for _ in range(N)]
    q = deque()
    q.append((N-1, M-1))
    d2[N-1][M-1] = 0
    while q:
        i, j = q.popleft()
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < N and 0 <= nj < M and d2[ni][nj] == -1:
                d2[ni][nj] = d2[i][j] + 1
                q.append((ni, nj))

    items = []
    for A, B, C, D in squares:
        if d1[A][B] == -1 or d2[A][B] == -1:
            continue
        d_total = d1[A][B] + d2[A][B]
        effective_gain = (C - 1) - (d_total - S)
        if effective_gain > 0:
            items.append((effective_gain, D))

    if not items:
        print(-1)
        return

    # DP for unbounded knapsack
    INF = float('inf')
    dp = [INF] * (required + 1)
    dp[0] = 0
    for gain, cost in items:
        for j in range(required + 1):
            if dp[j] != INF:
                new_j = min(j + gain, required)
                if dp[new_j] > dp[j] + cost:
                    dp[new_j] = dp[j] + cost

    if dp[required] == INF:
        print(-1)
    else:
        print(dp[required])

if __name__ == "__main__":
    main()
0