結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:08:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 213 ms / 5,000 ms
コード長 2,518 bytes
コンパイル時間 137 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 83,788 KB
最終ジャッジ日時 2025-03-20 21:09:30
合計ジャッジ時間 3,098 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    V = int(input[idx]); idx +=1
    O_x = int(input[idx]); idx +=1
    O_y = int(input[idx]); idx +=1
    
    has_oasis = not (O_x == 0 and O_y == 0)
    
    # Read the grid (y from 1 to N, each line is x from 1 to N)
    grid = [[0]*(N+1) for _ in range(N+1)]  # grid[y][x]
    for y in range(1, N+1):
        for x in range(1, N+1):
            grid[y][x] = int(input[idx])
            idx +=1
    
    max_health = [[[-1]*2 for _ in range(N+1)] for __ in range(N+1)]
    heap = []
    
    max_health[1][1][0] = V
    heapq.heappush(heap, (-V, 1, 1, 0))
    
    found = False
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]  # left, right, up, down
    
    while heap:
        neg_h, x, y, used = heapq.heappop(heap)
        current_h = -neg_h
        
        if current_h < max_health[x][y][used]:
            continue
        
        if x == N and y == N:
            found = True
            break
        
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            if 1 <= nx <= N and 1 <= ny <= N:
                new_h = current_h - grid[ny][nx]
                if new_h <= 0:
                    continue
                
                # Check if destination is reached
                if nx == N and ny == N:
                    found = True
                    break
                
                # Check if current cell is oasis and used is 0
                if has_oasis and nx == O_x and ny == O_y and used == 0:
                    # Option 1: do not use oasis
                    if new_h > max_health[nx][ny][0]:
                        max_health[nx][ny][0] = new_h
                        heapq.heappush(heap, (-new_h, nx, ny, 0))
                    
                    # Option 2: use oasis, double health and mark used as 1
                    new_h_doubled = new_h * 2
                    if new_h_doubled > max_health[nx][ny][1]:
                        max_health[nx][ny][1] = new_h_doubled
                        heapq.heappush(heap, (-new_h_doubled, nx, ny, 1))
                else:
                    # Proceed normally
                    if new_h > max_health[nx][ny][used]:
                        max_health[nx][ny][used] = new_h
                        heapq.heappush(heap, (-new_h, nx, ny, used))
        
        if found:
            break
    
    print("YES" if found else "NO")

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