Contest Duration: - (local time) (90 minutes) Back to Home

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 2013-11-14 06:44:18+0900 C - 暗闇帰り道 misolmiso Python (3.2.3) 0 1043 Byte WA 5039 ms 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