結果

問題 No.2366 登校
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:57:00
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,437 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 81,808 KB
実行使用メモリ 79,252 KB
最終ジャッジ日時 2025-06-12 19:57:35
合計ジャッジ時間 3,538 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left, bisect_right
import heapq

def main():
    N, M, K, T = map(int, input().split())
    mysterious = {}
    for _ in range(K):
        A, B, C, D = map(int, input().split())
        mysterious[(A-1, B-1)] = (C, D)  # Convert to 0-based indices

    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    visited = {}
    for i in range(N):
        for j in range(M):
            visited[(i, j)] = []
    start_i, start_j = 0, 0
    end_i, end_j = N-1, M-1

    heap = []
    heapq.heappush(heap, (0, 0, start_i, start_j))

    def is_dominated(entries, t, f):
        n = len(entries)
        if n == 0:
            return False
        idx = bisect_right(entries, (t, float('inf'))) - 1
        if idx >= 0:
            t_prime, f_prime = entries[idx]
            if t_prime <= t and f_prime <= f:
                return True
        return False

    def add_entry(entries, t, f):
        if is_dominated(entries, t, f):
            return False
        idx = bisect_left(entries, (t, f))
        entries.insert(idx, (t, f))
        i = idx + 1
        while i < len(entries):
            if entries[i][1] >= f:
                del entries[i]
            else:
                i += 1
        return True

    if add_entry(visited[(start_i, start_j)], 0, 0):
        pass

    found = False
    answer = -1

    while heap:
        f, t, i, j = heapq.heappop(heap)
        if i == end_i and j == end_j:
            answer = f
            found = True
            break
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < N and 0 <= nj < M:
                new_time = t + 1
                new_f = f
                if new_time > T:
                    continue
                entries = visited[(ni, nj)]
                if not is_dominated(entries, new_time, new_f):
                    if add_entry(entries, new_time, new_f):
                        heapq.heappush(heap, (new_f, new_time, ni, nj))
        if (i, j) in mysterious:
            C, D = mysterious[(i, j)]
            new_time = t + 1 - C
            new_f = f + D
            if new_time > T:
                continue
            entries = visited[(i, j)]
            if not is_dominated(entries, new_time, new_f):
                if add_entry(entries, new_time, new_f):
                    heapq.heappush(heap, (new_f, new_time, i, j))

    print(answer if found else -1)

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