Submission #1142248


Source Code Expand

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 Info

Submission Time
Task B - Food Collector
User nanae
Language Python (3.4.3)
Score 9605
Code Size 3142 Byte
Status AC
Exec Time 36 ms
Memory 6644 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 1158 / 20000 1363 / 20000 1020 / 20000 456 / 20000 1027 / 20000 1245 / 20000 1009 / 20000 773 / 20000 528 / 20000 1026 / 20000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
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