結果

問題 No.2366 登校
ユーザー lam6er
提出日時 2025-04-16 16:20:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,675 bytes
コンパイル時間 490 ms
コンパイル使用メモリ 81,524 KB
実行使用メモリ 79,568 KB
最終ジャッジ日時 2025-04-16 16:22:14
合計ジャッジ時間 2,191 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def main():
    import sys
    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 = int(input[idx]); idx +=1

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

    # Compute shortest path using BFS
    def bfs_shortest_path(N, M):
        start = (1, 1)
        end = (N, M)
        visited = [[-1] * (M + 1) for _ in range(N + 1)]
        q = deque([start])
        visited[1][1] = 0
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        while q:
            i, j = q.popleft()
            if (i, j) == end:
                return visited[i][j]
            for dx, dy in directions:
                ni, nj = i + dx, j + dy
                if 1 <= ni <= N and 1 <= nj <= M and visited[ni][nj] == -1:
                    visited[ni][nj] = visited[i][j] + 1
                    q.append((ni, nj))
        return -1  # unreachable according to problem statement

    L = bfs_shortest_path(N, M)
    if L <= T:
        print(0)
        return

    X = L - T
    if X <= 0:
        print(0)
        return

    # Separate squares into large and small
    squares_large = []
    squares_small = []
    for (A, B, C, D) in squares:
        c = C - 1
        if c >= X:
            squares_large.append(D)
        else:
            squares_small.append((c, D))

    min_d = float('inf')
    if squares_large:
        min_d = min(squares_large)

    if squares_small:
        max_c = max(c for (c, d) in squares_small)
        max_sum = X + max_c
        dp = [float('inf')] * (max_sum + 1)
        dp[0] = 0
        current_min_dp = float('inf')

        for (c, d) in squares_small:
            for y in range(max_sum + 1):
                if dp[y] != float('inf'):
                    new_y = y + c
                    new_cost = dp[y] + d
                    if new_y >= X:
                        if new_cost < current_min_dp:
                            current_min_dp = new_cost
                    else:
                        if new_y <= max_sum and new_cost < dp[new_y]:
                            dp[new_y] = new_cost

        # Check all y >= X in dp
        for y in range(X, max_sum + 1):
            if dp[y] < current_min_dp:
                current_min_dp = dp[y]

        if current_min_dp < min_d:
            min_d = current_min_dp

    if min_d == float('inf'):
        print(-1)
    else:
        print(min_d)

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