Submission #116795


Source Code Expand

Copy
N, M = map(int, input().strip().split())

C = list(['#' * (M + 2)] +
         ['#' + input().strip() + '#' for _ in range(N)] +
         ['#' * (M + 2)])

def get_C(place):
    n, m = place
    return C[n][m]

memo = [[0 for _ in l] for l in C]

def get_memo(place):
    n, m = place
    return memo[n][m]

def set_memo(place, value):
    n, m = place
    memo[n][m] = value

SP = divmod(''.join(C).find("s"), M + 2)


from collections import namedtuple

class P(namedtuple("P", ("brightness", "time", "place"))):
    __lt__ = lambda self, other: not super().__lt__(other)


D = [(-1, 0), (0, 1), (1, 0), (0, -1)]

from heapq import heappop, heappush

h = []
heappush(h, P(10, 0, SP))

while len(h) > 0:
    b, t, p = heappop(h)
    t_ = t + 1

    for d in D:
        p_ = tuple(map(sum, zip(p, d)))
        l = get_C(p_)

        if l == 'g':
            print(b)
            exit(0)

        if l in ('#', 's'):
            continue

        b_ = min(b, int(l) * 0.99 ** t_)
        
        if b_ > get_memo(p_):
            set_memo(p_, b_)
            heappush(h, P(b_, t_, p_))
print(-1)

Submission Info

Submission Time
Task C - 暗闇帰り道
User misolmiso
Language Python (3.2.3)
Score 0
Code Size 1154 Byte
Status WA
Exec Time 5043 ms
Memory 23340 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 16
WA × 37
TLE × 11
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 249 ms 8756 KB
00_mini_02.txt AC 149 ms 8724 KB
00_mini_03.txt AC 154 ms 8864 KB
00_mini_04.txt AC 146 ms 8860 KB
00_mini_05.txt AC 142 ms 8736 KB
00_sample_01.txt AC 160 ms 8860 KB
00_sample_02.txt AC 147 ms 8860 KB
01_rnd_01.txt TLE 5037 ms 17344 KB
01_rnd_02.txt WA 1092 ms 11576 KB
01_rnd_03.txt WA 237 ms 9344 KB
01_rnd_04.txt WA 651 ms 10140 KB
01_rnd_05.txt WA 205 ms 8988 KB
01_rnd_06.txt WA 164 ms 8860 KB
01_rnd_07.txt WA 220 ms 9368 KB
01_rnd_08.txt WA 1481 ms 11524 KB
01_rnd_09.txt WA 1974 ms 12348 KB
01_rnd_10.txt WA 3175 ms 12160 KB
01_rnd_11.txt WA 1764 ms 10880 KB
01_rnd_12.txt WA 1055 ms 10252 KB
01_rnd_13.txt WA 340 ms 9040 KB
01_rnd_14.txt WA 4017 ms 11356 KB
01_rnd_15.txt WA 1858 ms 10404 KB
01_rnd_16.txt AC 191 ms 9640 KB
01_rnd_17.txt AC 1602 ms 10140 KB
01_rnd_18.txt AC 151 ms 9016 KB
01_rnd_19.txt AC 157 ms 9496 KB
01_rnd_20.txt AC 151 ms 8988 KB
02_maxrnd_01.txt WA 2686 ms 14912 KB
02_maxrnd_02.txt WA 1891 ms 15168 KB
02_maxrnd_03.txt WA 2743 ms 14444 KB
02_maxrnd_04.txt WA 4439 ms 16448 KB
02_maxrnd_05.txt WA 3020 ms 14396 KB
02_maxrnd_06.txt TLE 5037 ms 15916 KB
02_maxrnd_07.txt WA 783 ms 12976 KB
02_maxrnd_08.txt WA 382 ms 12860 KB
02_maxrnd_09.txt TLE 5040 ms 15164 KB
02_maxrnd_10.txt WA 1682 ms 13140 KB
02_maxrnd_11.txt TLE 5036 ms 14784 KB
02_maxrnd_12.txt WA 3318 ms 13788 KB
02_maxrnd_13.txt WA 3909 ms 13488 KB
02_maxrnd_14.txt TLE 5043 ms 13360 KB
02_maxrnd_15.txt WA 785 ms 12700 KB
02_maxrnd_16.txt WA 3770 ms 12700 KB
02_maxrnd_17.txt WA 3214 ms 12700 KB
02_maxrnd_18.txt AC 285 ms 12700 KB
02_maxrnd_19.txt AC 246 ms 12700 KB
03_hard_01.txt TLE 5039 ms 21180 KB
03_hard_02.txt TLE 5037 ms 23340 KB
03_hard_03.txt WA 1736 ms 13616 KB
03_hard_04.txt WA 1803 ms 13760 KB
03_hard_05.txt TLE 5037 ms 19828 KB
03_hard_06.txt TLE 5039 ms 22392 KB
03_hard_07.txt WA 1733 ms 12700 KB
03_hard_08.txt WA 1774 ms 12740 KB
04_open_01.txt TLE 5039 ms 15044 KB
04_open_02.txt TLE 5038 ms 16320 KB
05_minihard_01.txt WA 181 ms 8836 KB
05_minihard_02.txt WA 182 ms 8860 KB
05_minihard_03.txt AC 160 ms 8780 KB
05_minihard_04.txt AC 161 ms 8844 KB
05_minihard_05.txt WA 176 ms 8860 KB
05_minihard_06.txt WA 181 ms 8856 KB
05_minihard_07.txt WA 157 ms 8812 KB
05_minihard_08.txt WA 164 ms 8768 KB