Educational DP Contest B --Frog 2 , il y a un cas où le code suivant devient inévitablement TLE, je l'ai donc soumis avec PyPy Il devient AC facilement. Quand j'ai enquêté plus tard, il a été constaté que le même algorithme peut être AC selon la langue utilisée ( référence ). Les utilisateurs de Python doivent choisir PyPy sauf s'ils utilisent une bibliothèque qui n'est pas implémentée dans PyPy. Cependant, soyez prudent car cela consomme beaucoup de mémoire. Quand je l'ai essayé avec Frog1, il consomme environ 4 fois plus de mémoire avec la même source.
| Langue | Mémoire |
|---|---|
| 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()