CSES - Array Division | Chia mảng

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

Bạn được cho một mảng chứa \(n\) số nguyên dương.

Nhiệm vụ của bạn là chia mảng thành \(k\) đoạn con sao cho tổng lớn nhất trong các đoạn con nhỏ nhất có thể.

Input

  • Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(k\): kích thước của mảng và số lượng đoạn con trong cách chia.
  • Dòng tiếp theo chứa \(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 lớn nhất của một đoạn con trong cách chia tối ưu.

Constraints

  • \(1 \leq n \leq 2 \cdot 10 ^ 5\)
  • \(1 \leq k \leq n\)
  • \(1 \leq x_i \leq 10 ^ 9\)

Example

Sample input

5 3
2 4 7 3 5

Sample output

8

Note

Một cách chia tối ưu là \([2,4],[7],[3,5]\) trong đó tổng của các đoạn con là \(6,7,8\). Tổng lớn nhất là tổng cuối cùng \(8\).

Bình luận