In Educational DP Contest B --Frog 2 , there is a case where the following code inevitably becomes TLE, so I submitted it with PyPy. By the way, it becomes AC easily. When I investigated later, it was found that the same algorithm may be AC depending on the language used ( reference ). Python users should choose PyPy, except in cases where they use libraries that are not implemented in PyPy. However, be careful as it consumes a lot of memory. When I tried it with Frog1, it consumes about 4 times more memory with the same source.
| language | memory |
|---|---|
| Python(3.82) | 20524 KB |
| PyPy3 (7.3.0) | 84904 KB |
import sys
sys.setrecursionlimit(250000)
input = sys.stdin.readline
def main():
n, k = map(int, input().split())
h = list(map(int,input().split()))
cost = [sys.maxsize]*n
cost[0] = 0
for i in range(0,n):
for j in range(1, k + 1):
if (i+ j>= n):
break
abs_ = abs(h[i] - h[i+j])
if cost[i+j] >cost[i] + abs_ :
cost[i+j] = cost[i] + abs_
print(cost[n-1])
main()
Recommended Posts