Sane's Monthly Algorithms Challenge: October 2008
Jumpscotch (Senior Level)
Hopscotch is a simple game which can be played with a group or family or individually. Diana has been playing the game for years and is easily the best Hopsscotch player on the playground. Her friends have decided to challenge her title by inventing a complicated version of Hopscotch called "Jumpscotch."
In Jumpscotch, a single row of squares is drawn along the ground and a positive integer is drawn inside each square. Starting on the first square, Diana must jump from square to square and finish on the last square. Afterwards, her 'score' is the sum of all numbers which she has touched. The objective of Jumpscotch is to get a lower score than your opponent.
Diana knows that she is only strong enough to hop a certain distance (d). She is also smart enough to know that with this limitation, the best 'path' is not always obvious. Diana wants your help in determining the best path, given each square's value and her maximum hopping distance.
On the first line, the integers n (1 ≤ n ≤ 1,000,000) and d (1 ≤ d ≤ 10).
There will be one test case where Diana has super human strength and d = 5,000 while n = 1,000,000.
The next n lines that follow have positive integers ≤ 1000, representing the number drawn inside each square. These lines are listed, in order, from start to finish.
On a single line, output the smallest possible score that Diana can obtain.
Point Value: 17 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Oct 20, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3