Chia Mảng Thành K Đoạn Tổng Nhỏ Nhất

General
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho một dãy gồm $N$ số nguyên dương $a_1, a_2, \dots, a_N$ và một số nguyên dương $K$ ($1 \le K \le N$). Bạn cần chia dãy thành tối đa $K$ đoạn con liên tiếp khác rỗng sao cho mỗi phần tử thuộc đúng một đoạn.

Hãy tìm giá trị nhỏ nhất có thể của tổng lớn nhất trong số các đoạn được chia.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên dương $N$ và $K$ ($1 \le K \le N \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên dương $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là giá trị nhỏ nhất của tổng đoạn lớn nhất.
Ví dụ
Input Output
5 3
2 4 7 3 5
8
Giới hạn
  • $1 \le K \le N \le 10^5$
  • $1 \le a_i \le 10^9$
Draft saved