DMOPC '14 Contest 5 P5 - Aircraft Carrier Akagi

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

It's time for Akagi's daily training!

Today, Akagi has set up N targets for herself placed in a line on the ocean. Each target is currently at a integer height H_i from 1 to 200\,000. Akagi can adjust the height of one target by one unit up or down in one nanosecond. There is no upper or lower limit to which Akagi may raise or lower the heights of the targets to. Akagi may even lower the targets to zero or negative height (in which case they'll be submerged under the ocean).

Akagi, being an Aircraft Carrier, plans to launch a single plane and attack a location beyond the K^{th} target (1 \le K \le N). However, the plane's flight path is a bit strange — on the targets that it passes over on its flight path, there must be an ascending path and a descending path of equal length. Additionally, the absolute difference in height between two adjacent targets on the flight path should be exactly 1.

Formally, Akagi needs to adjust the heights of the targets such that there exist two targets j and k (j \le k, j - 1 = k - j) and H_1 < H_2 < \dots < H_j > \dots > H_{k-1} > H_k and \left|H_i - H_{i+1}\right| = 1 (1 \le i < k). According to this definition, a single target (specifically, a path made up of only the first target) is a valid flight path.

It's no problem if the any of the targets (including the first) has a negative height — Akagi will simply ask for help from a Submarine Aircraft Carrier. When the deployed plane reaches the peak of the path (target j from above), it will drop a bomb that travels all the way to target k.

Completing this training exercise is vital to her performance reviews, so Akagi would like you to figure out the minimal time it takes for her to adjust the targets such that afterwards, there will be a valid flight path that finishes at or beyond the K^{th} target.


Subtask 1 [40%]

1 \le N \le 10\,000

Subtask 2 [60%]

1 \le N \le 200\,000

Input Specification

The first line of input will have two integers N and K separated by a single space.

The second line of input will have N space separated integers, H_1 \dots H_N.

Output Specification

The first line of output should be the minimal number of nanoseconds it takes Akagi to adjust all the targets for the plane. If it is not possible to adjust the targets in any amount of time, output -1.

Sample Input

5 4
1 5 2 6 2

Sample Output


Explanation for Sample Input

In the optimal solution, the final heights are 2, 3, 4, 3, 2. Akagi needs 1 + 2 + 2 + 3 + 0 = 8 nanoseconds to perform all the necessary adjustments.



There are no comments at the moment.