Submission #116801


Source Code Expand

Copy
from collections import namedtuple
from heapq import heappush, heappop

class P(tuple):
    __lt__ = lambda self, other: not super().__lt__(other)

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

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

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

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

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

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

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

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

h = [P((10.0, SP))]

while len(h) > 0:
    b, p = heappop(h)

    for d in D:
        #p_ = tuple(map(sum, zip(p, d)))
        p_ = (p[0] + d[0], p[1] + d[1])
        l = get_C(p_)
        
        if l == 's':
            print(b * 0.99)
            exit(0)
        
        if l in ('#', 'g'):
            continue

        b_ = min(float(l), b * 0.99)
        
        if b_ > get_memo(p_):
            set_memo(p_, b_)
            heappush(h, P((b_, p_)))

print(-1)

Submission Info

Submission Time
Task C - 暗闇帰り道
User misolmiso
Language Python (3.2.3)
Score 0
Code Size 1150 Byte
Status TLE
Exec Time 5041 ms
Memory 17404 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 58
TLE × 6
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 397 ms 8752 KB
00_mini_02.txt AC 145 ms 8848 KB
00_mini_03.txt AC 146 ms 8728 KB
00_mini_04.txt AC 146 ms 8848 KB
00_mini_05.txt AC 144 ms 8736 KB
00_sample_01.txt AC 153 ms 8740 KB
00_sample_02.txt AC 142 ms 8744 KB
01_rnd_01.txt AC 2948 ms 14496 KB
01_rnd_02.txt AC 970 ms 11304 KB
01_rnd_03.txt AC 204 ms 9020 KB
01_rnd_04.txt AC 431 ms 9592 KB
01_rnd_05.txt AC 229 ms 8860 KB
01_rnd_06.txt AC 181 ms 8856 KB
01_rnd_07.txt AC 188 ms 8988 KB
01_rnd_08.txt AC 825 ms 11228 KB
01_rnd_09.txt AC 2217 ms 13604 KB
01_rnd_10.txt AC 2013 ms 12880 KB
01_rnd_11.txt AC 1384 ms 11436 KB
01_rnd_12.txt AC 566 ms 10024 KB
01_rnd_13.txt AC 257 ms 8984 KB
01_rnd_14.txt AC 1782 ms 12512 KB
01_rnd_15.txt AC 566 ms 10460 KB
01_rnd_16.txt AC 158 ms 9388 KB
01_rnd_17.txt AC 165 ms 9912 KB
01_rnd_18.txt AC 169 ms 8860 KB
01_rnd_19.txt AC 156 ms 9312 KB
01_rnd_20.txt AC 162 ms 8744 KB
02_maxrnd_01.txt AC 2855 ms 15680 KB
02_maxrnd_02.txt AC 968 ms 13136 KB
02_maxrnd_03.txt AC 1810 ms 14016 KB
02_maxrnd_04.txt AC 1390 ms 13376 KB
02_maxrnd_05.txt AC 2020 ms 14256 KB
02_maxrnd_06.txt AC 4164 ms 16556 KB
02_maxrnd_07.txt AC 406 ms 12220 KB
02_maxrnd_08.txt AC 353 ms 12096 KB
02_maxrnd_09.txt AC 3300 ms 15808 KB
02_maxrnd_10.txt AC 524 ms 12252 KB
02_maxrnd_11.txt AC 2290 ms 14408 KB
02_maxrnd_12.txt AC 1570 ms 13620 KB
02_maxrnd_13.txt AC 1548 ms 13488 KB
02_maxrnd_14.txt AC 1903 ms 13912 KB
02_maxrnd_15.txt AC 771 ms 12476 KB
02_maxrnd_16.txt AC 2095 ms 14272 KB
02_maxrnd_17.txt AC 1870 ms 14052 KB
02_maxrnd_18.txt AC 244 ms 11872 KB
02_maxrnd_19.txt AC 183 ms 11708 KB
03_hard_01.txt TLE 5038 ms 17324 KB
03_hard_02.txt TLE 5041 ms 17320 KB
03_hard_03.txt AC 1300 ms 14800 KB
03_hard_04.txt AC 1273 ms 14784 KB
03_hard_05.txt TLE 5036 ms 17248 KB
03_hard_06.txt TLE 5038 ms 17200 KB
03_hard_07.txt AC 1313 ms 14704 KB
03_hard_08.txt AC 1284 ms 14776 KB
04_open_01.txt TLE 5037 ms 17404 KB
04_open_02.txt TLE 5036 ms 17340 KB
05_minihard_01.txt AC 163 ms 8736 KB
05_minihard_02.txt AC 161 ms 8736 KB
05_minihard_03.txt AC 149 ms 8740 KB
05_minihard_04.txt AC 149 ms 8728 KB
05_minihard_05.txt AC 162 ms 8728 KB
05_minihard_06.txt AC 163 ms 8796 KB
05_minihard_07.txt AC 147 ms 8740 KB
05_minihard_08.txt AC 150 ms 8768 KB