結果

問題 No.2366 登校
ユーザー gew1fw
提出日時 2025-06-12 14:59:35
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,801 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 77,420 KB
最終ジャッジ日時 2025-06-12 15:00:18
合計ジャッジ時間 2,341 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 4
権限があれば一括ダウンロードができます

ソースコード

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 = int(input[idx]); idx +=1

    grid = [[0 for _ in range(M)] for __ in range(N)]
    specials = []
    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
        specials.append( (A,B,C,D) )

    # Compute shortest path S using BFS
    start = (0,0)
    end = (N-1, M-1)
    visited = [[False]*M for __ in range(N)]
    q = deque()
    q.append( (start[0], start[1], 0) )
    visited[start[0]][start[1]] = True
    S = -1
    while q:
        r, c, dist = q.popleft()
        if r == end[0] and c == end[1]:
            S = dist
            break
        for dr, dc in [ (-1,0), (1,0), (0,-1), (0,1) ]:
            nr, nc = r + dr, c + dc
            if 0<=nr<N and 0<=nc<M and not visited[nr][nc]:
                visited[nr][nc] = True
                q.append( (nr, nc, dist +1) )
    if S == -1:
        print(-1)
        return

    if S <= T:
        print(0)
        return

    D = S - T

    eligible = []
    for A,B,C,D_i in specials:
        w = C - 1
        if w >0:
            eligible.append( (w, D_i) )

    if not eligible:
        print(-1)
        return

    # Check case 1: any single eligible w >= D
    min_single = None
    for w, v in eligible:
        if w >= D:
            if min_single is None or v < min_single:
                min_single = v

    candidates = []
    if min_single is not None:
        candidates.append(min_single)

    # For case 2: no single eligible, need to combine multiple
    # Sort eligible by v/w increasing
    eligible_sorted = sorted(eligible, key=lambda x: (x[1]/x[0], x[0]))
    # Try to use the top few items to reach the required D
    # Since D can be up to 1e9, we need a smarter way.

    # We'll consider up to 3 items, since beyond that it's too slow.
    # This is a heuristic and may not cover all cases.
    from itertools import combinations_with_replacement
    max_combinations = 3
    for k in range(1, max_combinations+1):
        for items in combinations_with_replacement(eligible_sorted, k):
            total_w = 0
            total_v = 0
            for (w, v) in items:
                total_w += w
                total_v += v
            if total_w >= D:
                candidates.append(total_v)

    # Also, consider items beyond the top 3, but this part is omitted due to time constraints.
    # The above code is just a heuristic and may not cover all cases.

    if not candidates:
        print(-1)
    else:
        print(min(candidates))

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