Дэд Хэсгийн Квадратууд

2s

512MB

1775

0%

Advanced Techniques

$n$ элементтэй массив өгөгдөв; үүнийг $k$ дэд хэсэгт хуваана. Дэд хэсэг бүрийн өртөг нь тухайн дэд хэсэг дэх утгуудын нийлбэрийн квадрат. Оновчтойгоор үйлдэхэд хамгийн бага нийт өртөг юу вэ?

https://cses.fi/problemset/task/2086

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $k$ : массивын элементүүд ба дэд хэсгүүдийн тоо. Массивын элементүүд $1,2,\dots,n$ гэж дугаарлагдана.

Хоёр дахь мөрөнд $n$ бүхэл тоо $x_1,x_2,\dots,x_n$ : массивын агуулга.

Гаралтын формат

Нэг бүхэл тоо хэвлэ: хамгийн бага нийт өртөг.

Хязгаарлалт

$1 \le k \le n \le 3000$
$1 \le x_i \le 10^5$

Жишээ

Оролт1

8 3
2 3 1 2 2 3 4 1

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...