RCO presents 日本橋ハーフマラソン 予選

Submission #1142248

Source codeソースコード

import sys
from heapq import heapify, heappush, heappop

sys.setrecursionlimit(10**5)
dx = [1,0,-1,0]
dy = [0,1,0,-1]
inf = float('inf')

def solve():
    # Input
    H, W, K, sr, sc = map(int, input().split())
    s = [[inf if j == '#' else 0 for j in input()] for i in range(H)]
    N = int(input())
    fd = dict()
    for i in range(N):
        fr, fc, F, D = map(int, input().split())
        fd[(fr-1, fc-1)] = (F, D)

    # Process
    ans = []
    ch = [s[i][:] for i in range(H)]
    ch[sr-1][sc-1] = 1
    inu2(H, W, K, 0, sr-1, sc-1, fd, ch, ans)

    # Output
    print(''.join(ans))

def inu2(H, W, K, t, a, b, fd, ch, ans):
    if t == K:
        return None

    mxhp = []
    i2c = ['D', 'R', 'U', 'L']
    c, d = 0, 0

    for i in range(4):
        if ch[a + dx[i]][b + dy[i]] == 0 and (a + dx[i], b + dy[i]) in fd:
            value = fd[(a + dx[i], b + dy[i])][0] - t * fd[(a + dx[i], b + dy[i])][1]

            if value > 0:
                heappush(mxhp, (-value, i))
            else:
                ch[a + dx[i]][b + dy[i]] = inf

    if mxhp:
        v, j = heappop(mxhp)
        ans.append(i2c[j])
        ch[a + dx[j]][b + dy[j]] += 1
        c = a + dx[j]
        d = b + dy[j]
    else:
        for i in range(4):
            if ch[a+dx[i]][b+dy[i]] != inf:
                heappush(mxhp, (ch[a+dx[i]][b+dy[i]], i))

        if mxhp:
            v, j = heappop(mxhp)
            ans.append(i2c[j])
            ch[a + dx[j]][b + dy[j]] += 1
            c = a + dx[j]
            d = b + dy[j]
        else:
            ans.append('-')
            c, d = a, b

    return inu2(H, W, K, t + 1, c, d, fd, ch, ans)





def inu1_oukyu(H, W, K, t, a, b, fd, ch, ans):
    if t == K:
        return None
    elif t > K//2:
        ans.append('-')
        return inu1_oukyu(H, W, K, t + 1, a, b, fd, ch, ans)

    mxhp = []
    i2c = ['D', 'R', 'U', 'L']
    c, d = 0, 0

    for i in range(4):
        if ch[a + dx[i]][b + dy[i]] == 0 and (a + dx[i], b + dy[i]) in fd:
            value = fd[(a + dx[i], b + dy[i])][0] - t * fd[(a + dx[i], b + dy[i])][1]

            if value > 0:
                heappush(mxhp, (-value, i))
            else:
                ch[a + dx[i]][b + dy[i]] = inf

    if mxhp:
        v, j = heappop(mxhp)
        ans.append(i2c[j])
        ch[a + dx[j]][b + dy[j]] += 1
        c = a + dx[j]
        d = b + dy[j]
    else:
        for i in range(4):
            if ch[a+dx[i]][b+dy[i]] != inf:
                heappush(mxhp, (ch[a+dx[i]][b+dy[i]], i))

        if mxhp:
            v, j = heappop(mxhp)
            ans.append(i2c[j])
            ch[a + dx[j]][b + dy[j]] += 1
            c = a + dx[j]
            d = b + dy[j]
        else:
            ans.append('-')
            c, d = a, b

    return inu1_oukyu(H, W, K, t + 1, c, d, fd, ch, ans)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission

Task問題 B - Food Collector
User nameユーザ名 nanae
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 AC
Score得点 9605
Source lengthソースコード長 3142 Byte
File nameファイル名
Exec time実行時間 36 ms
Memory usageメモリ使用量 6644 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 1158 / 20000 subtask_01_01.txt
test_02 1363 / 20000 subtask_01_02.txt
test_03 1020 / 20000 subtask_01_03.txt
test_04 456 / 20000 subtask_01_04.txt
test_05 1027 / 20000 subtask_01_05.txt
test_06 1245 / 20000 subtask_01_06.txt
test_07 1009 / 20000 subtask_01_07.txt
test_08 773 / 20000 subtask_01_08.txt
test_09 528 / 20000 subtask_01_09.txt
test_10 1026 / 20000 subtask_01_10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 35 ms 6636 KB
subtask_01_02.txt AC 36 ms 6644 KB
subtask_01_03.txt AC 35 ms 6516 KB
subtask_01_04.txt AC 34 ms 6516 KB
subtask_01_05.txt AC 35 ms 6516 KB
subtask_01_06.txt AC 35 ms 6516 KB
subtask_01_07.txt AC 34 ms 6516 KB
subtask_01_08.txt AC 34 ms 6516 KB
subtask_01_09.txt AC 34 ms 6508 KB
subtask_01_10.txt AC 35 ms 6516 KB