Chia Mảng

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho mảng $n$ số nguyên dương. Chia mảng thành đúng $k$ mảng con liên tiếp sao cho tổng lớn nhất trong các mảng con là nhỏ nhất có thể. In ra giá trị tổng lớn nhất tối thiểu đó.

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $k$ .
Dòng 2: $n$ số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In một số nguyên — tổng lớn nhất nhỏ nhất có thể đạt được.

Ràng buộc

$1 \leq k \leq n \leq 2 \cdot 10^{5}$
$1 \leq a_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
5 3 2 4 7 3 5	8	Chia thành $[2, 4], [7], [3, 5]$ với tổng 6, 7, 8. Tổng lớn nhất tối thiểu = 8.
4 2 3 2 1 4	5	Chia $[3, 2], [1, 4]$ : tổng 5, 5. Tổng lớn nhất = 5 — tốt hơn mọi cách chia khác.

Bình luận

Không có bình luận tại thời điểm này.