Trò chơi của VOVA

View as PDF

Submit solution

Points: 1.08 (partial)
Time limit: 6.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đây là trò chơi một người tạm gọi là bạn Vova với hai dãy số nguyên dương: ~a~ gồm ~n > 1~ phần tử và ~b~ gồm ~m > 1~ phần tử. Vova phải thực hiện các thao tác sau đây:

  • Chia mỗi dãy ~a~ và ~b~ thành ~k > 0~ nhóm, mỗi nhóm gồm dãy các phần tử đứng liền nhau, số phần tử của mỗi nhóm có thể khác nhau nhưng tối thiểu phải là ~1~. Số ~k~ do Vova tự quyết định; Mã số các nhóm là ~1~, ~2~, ..., k;
  • Với mỗi nhóm ~i~ trong dãy ~a~ Vova phải tính tổng ~c~ = ~c_{1}~ + ~c_{2}~ + ...+ ~c_{k}~

trong đó:

  • ~c_{i}~ = (~s_{i}~ - ~u_{i}~)(~t_{i}~ - ~v_{i}~), ~i~ = ~1~, ~2~, ..., k;
  • ~s_{i}~ là tổng các phần tử của nhóm ~i~ trong dãy a;
  • ~u_{i}~ là số phần tử của nhóm ~i~ trong dãy a;
  • ~t_i~ là tổng các phần tử của nhóm ~i~ trong dãy b;
  • ~v_{i}~ là số phần tử của nhóm ~i~ trong dãy b;

Hãy cho biết giá trị min của ~c~.

Input

Dòng đầu tiên: ~2~ số ~n~ và ~m~ (~n~, ~m \leq~ ~10^4~)

Tiếp đến là ~n~ phần tử của dãy a;

Tiếp đến là ~m~ phần tử của dãy ~b~

(~1 \leq a_{i}~, ~b_{i} \leq~ ~10^5~)

Output

Chứa giá trị min ~c~.

Sample Input

3 2
3 7 4
5 2

Sample Output

17

Comments

Please read the guidelines before commenting.


There are no comments at the moment.