Bình Phương Các Khối · canuc80k4100

Cho một dãy gồm $n$ số nguyên dương. Bạn phải đặt các ranh giới để chia toàn bộ dãy thành đúng $k$ đoạn liên tiếp không rỗng.

Với mỗi đoạn, gọi $S$ là tổng các phần tử trong đoạn đó. Chi phí của đoạn bằng $S^{2}$ . Tổng chi phí của một cách chia là tổng chi phí của $k$ đoạn. Hãy tìm tổng chi phí nhỏ nhất có thể đạt được.

Input

Dòng đầu chứa hai số nguyên $n$ và $k$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ theo đúng thứ tự của dãy.

Output

In ra một số nguyên: tổng chi phí nhỏ nhất khi chia dãy thành đúng $k$ đoạn.

Constraints

$1 \leq k \leq n \leq 3000$ .
$1 \leq a_{i} \leq 1 0^{5}$ với mọi $1 \leq i \leq n$ .
Mọi đoạn đều phải chứa ít nhất một phần tử.
Kết quả phù hợp với số nguyên có dấu $64$ bit.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 80$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

5 2
1 3 2 4 2

Output

Giải thích: Chia sau phần tử thứ ba tạo hai đoạn có tổng lần lượt là $6$ và $6$ . Tổng chi phí bằng $6^{2} + 6^{2} = 72$ , và không có vị trí chia nào cho kết quả nhỏ hơn.

Mô hình quy hoạch động: Đặt P[i] là tổng của a_1..a_i. Chi phí đoạn (p+1)..i là (P[i]-P[p])². Gọi dp[g][i] là chi phí nhỏ nhất để chia i phần tử đầu thành đúng g đoạn. Điểm chia cuối cùng cho công thức
Mô hình quy hoạch động: dp[g][i] = min(dp[g-1][p] + (P[i]-P[p])²) với g-1 ≤ p < i.
Tối ưu Divide and Conquer: Hàm chi phí đoạn là Monge vì các phần tử đều dương. Với bốn biên theo thứ tự, khai triển bất đẳng thức tứ giác cho phần chênh lệch bằng âm hai lần tích của hai tổng không âm. Do đó vị trí tối ưu trên cùng một hàng DP không giảm khi i tăng. Ta tính mỗi hàng bằng chia để trị: giải vị trí giữa, quét điểm chia trong khoảng tối ưu hiện tại, rồi dùng điểm tốt nhất làm cận cho hai nửa.
Chứng minh đúng: Mỗi cách chia i phần tử thành g đoạn có duy nhất một điểm chia cuối p, nên công thức DP xét đủ và chỉ xét các cách hợp lệ. Prefix sum tính đúng chi phí đoạn cuối. Tính đơn điệu của điểm tối ưu bảo đảm thủ tục chia để trị không loại bỏ điểm chia tốt nhất ở bất kỳ vị trí nào. Vì vậy hàng sau được tính đúng từ hàng trước, và cuối cùng dp[k][n] là đáp án.
Độ phức tạp: Thời gian O(k n log n), bộ nhớ O(n) ngoài prefix sum.