Appleman và Toastman

Điểm: 3,00 (OI)

Giới hạn thời gian: 2.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

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Appleman và Toastman chơi một trò chơi. Ban đầu, Appleman đưa cho Toastman một nhóm gồm $n$ số. Sau đó, hai người lặp lại các thao tác sau:

Mỗi khi Toastman nhận được một nhóm số, anh ta cộng tổng các số trong nhóm vào điểm chung, rồi đưa nhóm đó cho Appleman.
Mỗi khi Appleman nhận được một nhóm chỉ có một số, anh ta vứt nhóm đó đi. Nếu nhóm có nhiều hơn một số, anh ta chia nhóm thành hai nhóm con không rỗng (theo cách tuỳ ý) và đưa cả hai cho Toastman.

Sau khi cả hai hoàn tất mọi thao tác, hãy xác định giá trị lớn nhất của điểm có thể đạt được.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ — các số trong nhóm khởi tạo.

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị lớn nhất của điểm.

Ràng buộc

$1 \leq n \leq 3 \cdot 10^{5}$
$1 \leq a_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
1 10	10	Chỉ có một số nên Toastman cộng $10$ , sau đó Appleman vứt đi.
3 3 1 5	26	Toastman nhận $[3, 1, 5]$ cộng $9$ . Appleman chia thành $[3, 5]$ và $[1]$ . Toastman cộng $1$ rồi cộng $8$ . Appleman chia $[3, 5]$ thành $[3]$ và $[5]$ , Toastman cộng $3$ và $5$ . Tổng: $9 + 1 + 8 + 3 + 5 = 26$ .
2 1 1	4	Toastman cộng $2$ , sau khi tách lại cộng $1 + 1$ . Tổng $4$ .

Bình luận

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