結果

問題 No.2366 登校
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:54:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 164 ms / 4,000 ms
コード長 5,153 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 82,844 KB
実行使用メモリ 79,600 KB
最終ジャッジ日時 2025-06-20 11:31:07
合計ジャッジ時間 3,858 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

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

    magic = {}
    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
        magic[(A,B)] = (C, D)

    # Directions: up, down, left, right
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]

    # For each cell (i,j), keep a list of (time, fatigue) sorted by time
    state = [[[] for _ in range(M)] for _ in range(N)]

    heap = []
    heapq.heappush(heap, (0, 0, 0, 0))  # (fatigue, time, i, j)
    state[0][0].append( (0, 0) )

    found = False
    answer = -1

    while heap:
        d, t, i, j = heapq.heappop(heap)
        if i == N-1 and j == M-1:
            if t <= T:
                answer = d
                found = True
                break
            else:
                continue

        # If this state is outdated, skip
        current_list = state[i][j]
        # Binary search to check if this state is valid
        left, right = 0, len(current_list)
        while left < right:
            mid = (left + right) // 2
            if current_list[mid][0] <= t:
                left = mid +1
            else:
                right = mid
        pos = left -1
        if pos <0 or current_list[pos][1] < d:
            continue

        # Generate moves
        for di, dj in dirs:
            ni = i + di
            nj = j + dj
            if 0<=ni<N and 0<=nj<M:
                new_time = t +1
                new_d = d
                # Check if this state can be added to ni, nj
                target_list = state[ni][nj]
                insert_pos = len(target_list)
                for idx_in_list in range(len(target_list)):
                    ct, cd = target_list[idx_in_list]
                    if ct <= new_time and cd <= new_d:
                        insert_pos = -1
                        break
                    if ct >= new_time:
                        insert_pos = idx_in_list
                        break
                if insert_pos == -1:
                    continue
                # Now check from insert_pos backwards
                new_entries = []
                added = False
                # Check previous entries
                if insert_pos >0:
                    prev_t, prev_d = target_list[insert_pos-1]
                    if prev_t <= new_time and prev_d <= new_d:
                        continue
                # Remove all entries after insert_pos that have time >= new_time and d >= new_d
                start = insert_pos
                while start < len(target_list):
                    ct, cd = target_list[start]
                    if ct < new_time:
                        start +=1
                        continue
                    if cd >= new_d:
                        break
                    else:
                        start +=1
                # The entries from insert_pos to start-1 are to be removed
                # The new entry is (new_time, new_d)
                # So, target_list becomes target_list[:insert_pos] + [new_entry] + target_list[start:]
                new_entry = (new_time, new_d)
                new_target_list = target_list[:insert_pos] + [new_entry] + target_list[start:]
                state[ni][nj] = new_target_list
                heapq.heappush(heap, (new_d, new_time, ni, nj))

        # Check if current cell is magic
        if (i,j) in magic:
            C, D_val = magic[(i,j)]
            new_time = t - C +1
            new_d = d + D_val
            # Check if this state can be added to i,j
            target_list = state[i][j]
            insert_pos = len(target_list)
            for idx_in_list in range(len(target_list)):
                ct, cd = target_list[idx_in_list]
                if ct <= new_time and cd <= new_d:
                    insert_pos = -1
                    break
                if ct >= new_time:
                    insert_pos = idx_in_list
                    break
            if insert_pos == -1:
                continue
            # Check previous entries
            added = False
            if insert_pos >0:
                prev_t, prev_d = target_list[insert_pos-1]
                if prev_t <= new_time and prev_d <= new_d:
                    continue
            # Remove entries that are dominated
            start = insert_pos
            while start < len(target_list):
                ct, cd = target_list[start]
                if ct < new_time:
                    start +=1
                    continue
                if cd >= new_d:
                    break
                else:
                    start +=1
            new_entry = (new_time, new_d)
            new_target_list = target_list[:insert_pos] + [new_entry] + target_list[start:]
            state[i][j] = new_target_list
            heapq.heappush(heap, (new_d, new_time, i, j))

    print(answer if found else -1)

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