Đọc Sách

Đ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

Có $n$ quyển sách, sách thứ $i$ cần $t_{i}$ giây để đọc. Hai người cần đọc hết tất cả các sách, mỗi người phải đọc từng quyển từ đầu đến cuối. Hai người không được đọc cùng một quyển sách cùng lúc nhưng có thể đọc các sách khác nhau đồng thời. Hãy tính thời gian tối thiểu để cả hai hoàn thành tất cả sách.

Dữ liệu vào

Dòng 1: số nguyên $n$ .
Dòng 2: $n$ số nguyên $t_{1}, t_{2}, \dots, t_{n}$ .

Dữ liệu ra

In một số nguyên — thời gian tối thiểu.

Ràng buộc

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

Ví dụ

Input	Output	Giải thích
3 2 8 3	16	Sách dày nhất (t=8) là nút thắt cổ chai. Đáp án = max(2+8+3, 2×8) = max(13, 16) = 16.
3 3 3 3	9	Tổng = 9, max = 3, đáp án = max(9, 6) = 9. Hai người có thể đọc xen kẽ nhau hoàn hảo.

Bình luận

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