COCI '18 Contest 6 #4 Simfonija

View as PDF

Submit solution

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

Problem types
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

Almost no one believed in the virtuous abilities of the composer Marin. Specifically, not until the day he composed his 9th symphony.

The symphony can be represented as a series of frequencies that are integer numbers. In order for Marin to prove his talent and demonstrate that this symphony is not just one of many, he decided to compare it with the ancient symphony "Little Night Fiesta" of the best musician in history, Stjepan. In the stars it is written that the lengths of these two symphonies are equal to N.

Marin compares the symphonies by writing them one under the other to a piece of paper. The symphony diversity is defined as the sum of the absolute differences of the corresponding frequencies. The diversity of symphonies A and B of length N is:

\displaystyle \sum_{i=1}^{N} ~|A_i - B_i|~

Before comparing the two symphonies, Marin will do two things. First, he will modulate his symphony by adding an integer number X to each frequency. Then he will change no more than K frequencies to some other arbitrary frequency value because he had a vision in the dream as well as every top author.

Marin will choose X and change some K frequencies so that his symphony is as similar to Stjepan's, i.e. so the defined diversity is minimal. Help Marin and calculate the smallest possible diversity to Stjepan's symphony.


In the first line there are integer numbers N and K (1 \le N \le 100\,000, 0 \le K \le N), numbers from the task's text.

In the second line there are N integers A_i (-1\,000\,000 \le A_i \le 1\,000\,000) which represent frequencies of Marin's symphony.

In the third line there are N integers B_i (-1\,000\,000 \le B_i \le 1\,000\,000) which represent frequencies of Stjepan's symphony.


In the only line print out the smallest possible diversity between Marin and Stjepan's symphony.


In the test samples totally worth 40% of the points it will hold K = 0.

Sample Input 1

3 0
1 2 3
4 5 7

Sample Output 1


Sample Input 2

3 1
1 2 3
4 5 7

Sample Output 2


Explanation for Sample Output 2

If Marin modulates his symphony for X = 3 and changes the last frequency to 7, his symphony will then be completely equal to Stjepan's, so the required diversity is 0.

Sample Input 3

4 1
1 2 1 2
5 6 7 8

Sample Output 3



There are no comments at the moment.