Hộp đựng chuông

Điểm: 4,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Kevin có một bộ sưu tập $n$ chiếc chuông đeo cổ bò, kích thước nguyên dương được cho theo thứ tự không giảm $s_{1} \leq s_{2} \leq \dots \leq s_{n}$ . Anh cần xếp toàn bộ $n$ chiếc chuông vào đúng $k$ chiếc hộp, mỗi hộp chứa tối đa hai chuông.

Một hộp có kích thước $s$ chứa được một hoặc hai chuông nếu tổng kích thước của chúng không vượt quá $s$ .

Hãy xác định kích thước nhỏ nhất $s$ sao cho có thể xếp toàn bộ $n$ chuông vào $k$ hộp có cùng kích thước $s$ .

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $k$ .
Dòng 2: $n$ số nguyên $s_{1}, s_{2}, \dots, s_{n}$ theo thứ tự không giảm.

Dữ liệu ra

In ra một số nguyên duy nhất: kích thước nhỏ nhất $s$ cần thiết.

Ràng buộc

$1 \leq n \leq 2 k \leq 100 000$
$1 \leq s_{1} \leq s_{2} \leq \dots \leq s_{n} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
2 1 2 5	7	Hai chuông phải vào chung hộp duy nhất, tổng kích thước $2 + 5 = 7$ .
4 3 2 3 5 9	9	Một cách xếp tối ưu: ${2, 3}$ , ${5}$ , ${9}$ — hộp lớn nhất chứa chuông kích thước $9$ .
3 2 3 5 7	8	Xếp ${3, 5}$ và ${7}$ , kích thước hộp lớn nhất là $3 + 5 = 8$ .

Bình luận

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