CSES - Subarray Squares | Bình phương mảng con

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
tan , kitsune
Dạng bài
Điểm: 2300 (p) Thời gian: 1.5s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một mảng gồm \(n\) phần tử, nhiệm vụ của bạn là chia thành \(k\) mảng con. Chi phí của mỗi mảng con là bình phương của tổng của các giá trị trong mảng con. Tổng chi phí tối thiểu là bao nhiêu nếu bạn hành động một cách tối ưu?

Input

  • Dòng đầu vào đầu có hai số nguyên \(n\) và \(k\): các phần tử của mảng và số lượng mảng con. Các phần tử của mảng được đánh số \(1, 2, \ldots, n\).
  • Dòng thứ hai có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng.

Output

  • In một số nguyên: tổng chi phí tối thiểu.

Constraints

  • \(1 \le k \le n \le 3000\)
  • \(1 \le x_i \le 10^5\)

Example

Sample input

8 3
2 3 1 2 2 3 4 1

Sample output

110

Note

Một giải pháp tối ưu là \([2,3,1]\), \([2,2,3]\), \([4,1]\), chi phí của nó là \((2 + 3 + 1)^2 + (2 + 2 + 3)^2 + (4 + 1)^2 = 110\).

Bình luận