Educational DP Contest AtCoder B - Frog 2

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 1G

Problem type

There are N stones, numbered 1, 2, \dots, N. For each i (1 \le i \le N), the height of Stone i is h_i.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone N:

  • If the frog is currently on Stone i, jump to one of the following: Stone i+1, i+2, \dots, i+K. Here, a cost of |h_i-h_j| is incurred, where j is the stone to land on.

Find the minimum possible total cost incurred before the frog reaches Stone N.

Constraints

  • All values in input are integers.
  • 2 \le N \le 10^5
  • 1 \le K \le 100
  • 1 \le h_i \le 10^4

Input Specification

The first line of input will contain 2 integers N and K.

The second line of input will contain N spaced integers, h_i, the height of stone i.

Output Specification

Output a single integer, the minimum possible total cost incurred.

Sample Input 1

5 3
10 30 40 50 20

Sample Output 1

30

Sample Input 2

3 1
10 20 10

Sample Output 2

20

Sample Input 3

2 100
10 10

Sample Output 3

0

Sample Input 4

10 4
40 10 20 70 80 10 20 70 80 60

Sample Output 4

40

Sample Explanations

For the first sample, if we follow the path 1 \to 2 \to 5, the total cost incurred would be |10-30| + |30-20| = 30.

For the second sample, if we follow the path 1 \to 2 \to 3, the total cost incurred would be |10-20| + |20-10| = 20.

For the third sample, if we follow the path 1 \to 2, the total cost incurred would be |10-10| = 0.

For the fourth sample, if we follow the path 1 \to 4 \to 8 \to 10, the total cost incurred would be |40-70| + |70-70| + |70-60| = 40.


Comments


  • -1
    AndyZhang68  commented on June 17, 2024, 3:40 a.m.

    pypy is recommended for python submissions to not TLE