COCI '15 Contest 6 #5 Krumpirko

View as PDF

Submit solution

Points: 15 (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

Young Mr. Potato is opening two new stores where he will, you guessed it, sell potatoes. Mr. Potato gets his potatoes from N farmers. Each farmer offers exactly a_i potatoes per bag for a total price of c_i. Mr. Potato is going to buy all bags of potatoes from all farmers and place the bags in his two stores.

Let's denote the average potato price in the first store with P_1, and the average potato price in the second store with P_2. The average potato price in a store is equal to the ratio of the price and the total number of potatoes in the store. Taking into account logistical difficulties and the amount of potatoes in the stores, he wants the product of the average prices of potatoes in the stores to be minimal. In other words, he wants the product of P_1 and P_2 to be minimal.

After Mr. Potato settles on a division of bags in the stores, at least one store must have exactly L bags.


The first line of input contains two integers N and L (2 \le N \le 100, 1 \le L < N), the number of potato bags and the number of potato bags in at least one store.

The second line of input contains N integers a_i (1 \le a_i \le 100), separated by space.

The third line of input contains N integers c_i (1 \le c_i \le 1\,000\,000), separated by space.

The sum of all a_i will be \le 500.


The first and only line of output must contain the minimal product of P_1 and P_2 from the task, rounded to three decimal places.


In at least 30\% of examples, it will hold N \le 20.

Sample Input 1

3 1
3 2 1
1 2 3

Sample Output 1


Sample Input 2

3 2
2 2 2
3 3 3

Sample Output 2



There are no comments at the moment.