Buggy python submission (verdict: Time Limit Exceeded):

def main():
    n, k = map(int,input().split())
    h = list(map(int,input().split()))

    dp = [-1] * n
    dp[0] = 0
    for i in range(n):
        lmt = min(i+k+1,n)
        for j in range(i+1,lmt):
            tmp = dp[i] + abs(h[i]-h[j])
            if dp[j] == -1 or dp[j] > tmp:
                dp[j] = tmp
    print(dp[n-1])
    
if __name__=='__main__':
    main()


Fixed submission:

def main():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[None]*n
    temp=[1001]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        low=i-k-1
        if low<0:
            low=-1
        for j in range(i-1,low,-1):
            temp[j]=dp[j]+abs(h[i]-h[j])
            if j==i-1:
                mn=temp[j]
            else:
                if mn > temp[j]:
                    mn=temp[j]
        # temp2=dp[i-2]+abs(h[i]-h[i-2])
        # temp1=dp[i-1]+abs(h[i]-h[i-1])
        dp[i]=mn
        #temp=[1001]*n
    print(dp[n-1])

if __name__=='__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):

def main():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[None]*n
    temp=[1001]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        low=i-k-1
        if low<0:
            low=-1
        for j in range(i-1,low,-1):
            temp[j]=dp[j]+abs(h[i]-h[j])
            if j==i-1:
                mn=temp[j]
            else:
                if mn > temp[j]:
                    mn=temp[j]
        # temp2=dp[i-2]+abs(h[i]-h[i-2])
        # temp1=dp[i-1]+abs(h[i]-h[i-1])
        dp[i]=mn
        temp=[1001]*n
    print(dp[n-1])

if __name__=='__main__':
    main()


Fixed submission:

def main():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[None]*n
    temp=[1001]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        low=i-k-1
        if low<0:
            low=-1
        for j in range(i-1,low,-1):
            temp[j]=dp[j]+abs(h[i]-h[j])
            if j==i-1:
                mn=temp[j]
            else:
                if mn > temp[j]:
                    mn=temp[j]
        # temp2=dp[i-2]+abs(h[i]-h[i-2])
        # temp1=dp[i-1]+abs(h[i]-h[i-1])
        dp[i]=mn
        #temp=[1001]*n
    print(dp[n-1])

if __name__=='__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):

def main():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[None]*n
    temp=[1001]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        low=i-k-1
        if low<0:
            low=-1
        for j in range(i-1,low,-1):
            temp[j]=dp[j]+abs(h[i]-h[j])

        # temp2=dp[i-2]+abs(h[i]-h[i-2])
        # temp1=dp[i-1]+abs(h[i]-h[i-1])
        dp[i]=min(temp)
        temp=[1001]*n
    print(dp[n-1])

if __name__=='__main__':
    main()


Fixed submission:

def main():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[None]*n
    temp=[1001]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        low=i-k-1
        if low<0:
            low=-1
        for j in range(i-1,low,-1):
            temp[j]=dp[j]+abs(h[i]-h[j])
            if j==i-1:
                mn=temp[j]
            else:
                if mn > temp[j]:
                    mn=temp[j]
        # temp2=dp[i-2]+abs(h[i]-h[i-2])
        # temp1=dp[i-1]+abs(h[i]-h[i-1])
        dp[i]=mn
        #temp=[1001]*n
    print(dp[n-1])

if __name__=='__main__':
    main()