Submission #116794


Source Code Expand

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

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

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

def see(place, table):
    n, m = place
    return table[n][m]

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 = see(p_, C)

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

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

        b_ = int(l) * 0.99 ** t_
        m = see(p_, memo)
        
        if b_ > m:
            memo[p_[0]][p_[1]] = 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 1043 Byte
Status WA
Exec Time 5039 ms
Memory 24288 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 15
WA × 23
TLE × 26
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 424 ms 8680 KB
00_mini_02.txt AC 144 ms 8724 KB
00_mini_03.txt AC 145 ms 8744 KB
00_mini_04.txt AC 146 ms 8740 KB
00_mini_05.txt AC 146 ms 8764 KB
00_sample_01.txt AC 181 ms 8856 KB
00_sample_02.txt WA 156 ms 8856 KB
01_rnd_01.txt TLE 5038 ms 20748 KB
01_rnd_02.txt WA 3343 ms 14668 KB
01_rnd_03.txt WA 281 ms 9356 KB
01_rnd_04.txt WA 2542 ms 12680 KB
01_rnd_05.txt WA 297 ms 9140 KB
01_rnd_06.txt WA 168 ms 8972 KB
01_rnd_07.txt WA 259 ms 9372 KB
01_rnd_08.txt TLE 5039 ms 15216 KB
01_rnd_09.txt TLE 5037 ms 15860 KB
01_rnd_10.txt TLE 5035 ms 14712 KB
01_rnd_11.txt TLE 5036 ms 12712 KB
01_rnd_12.txt WA 3229 ms 11792 KB
01_rnd_13.txt WA 679 ms 9240 KB
01_rnd_14.txt TLE 5036 ms 12536 KB
01_rnd_15.txt WA 4736 ms 11588 KB
01_rnd_16.txt WA 170 ms 9628 KB
01_rnd_17.txt AC 2612 ms 10936 KB
01_rnd_18.txt AC 156 ms 8892 KB
01_rnd_19.txt AC 160 ms 9428 KB
01_rnd_20.txt AC 153 ms 8972 KB
02_maxrnd_01.txt TLE 5036 ms 19672 KB
02_maxrnd_02.txt TLE 5037 ms 21080 KB
02_maxrnd_03.txt TLE 5038 ms 18840 KB
02_maxrnd_04.txt TLE 5038 ms 19520 KB
02_maxrnd_05.txt TLE 5036 ms 17616 KB
02_maxrnd_06.txt TLE 5036 ms 17504 KB
02_maxrnd_07.txt WA 1899 ms 14680 KB
02_maxrnd_08.txt WA 764 ms 13228 KB
02_maxrnd_09.txt TLE 5035 ms 17088 KB
02_maxrnd_10.txt TLE 5037 ms 16432 KB
02_maxrnd_11.txt TLE 5037 ms 16428 KB
02_maxrnd_12.txt TLE 5037 ms 15584 KB
02_maxrnd_13.txt TLE 5037 ms 15160 KB
02_maxrnd_14.txt TLE 5036 ms 14580 KB
02_maxrnd_15.txt WA 1746 ms 12860 KB
02_maxrnd_16.txt TLE 5036 ms 13908 KB
02_maxrnd_17.txt TLE 5036 ms 14144 KB
02_maxrnd_18.txt AC 339 ms 12720 KB
02_maxrnd_19.txt AC 252 ms 12692 KB
03_hard_01.txt TLE 5038 ms 20392 KB
03_hard_02.txt TLE 5037 ms 24288 KB
03_hard_03.txt WA 1660 ms 13612 KB
03_hard_04.txt WA 1730 ms 13752 KB
03_hard_05.txt TLE 5036 ms 20540 KB
03_hard_06.txt TLE 5039 ms 23976 KB
03_hard_07.txt WA 1677 ms 13756 KB
03_hard_08.txt WA 1726 ms 13760 KB
04_open_01.txt TLE 5036 ms 15324 KB
04_open_02.txt TLE 5037 ms 18132 KB
05_minihard_01.txt WA 287 ms 9404 KB
05_minihard_02.txt WA 209 ms 8972 KB
05_minihard_03.txt AC 160 ms 8852 KB
05_minihard_04.txt AC 159 ms 8860 KB
05_minihard_05.txt WA 261 ms 9116 KB
05_minihard_06.txt WA 210 ms 8988 KB
05_minihard_07.txt WA 156 ms 8860 KB
05_minihard_08.txt AC 163 ms 8776 KB