ACM - ACM
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

An là môt người rất đam mê lập trình, đặc biệc là các thuật toán. Cậu ta đã quyết tâm tập luyện rất nhiều và đã trở thành một ACMer rất mạnh. Năm 2020, cậu tham gia kì thi ACM-ICPC Vietnam National Programming Contest. An mạnh đến mức mà cậu ta có thể xác định được mình sẽ mất chính xác bao nhiêu thời gian để giải được bài thứ i và đặc biệt là cậu ta chỉ cần submit đúng một lần duy nhất là có thể Accepted, vấn đề còn lại chỉ đơn giản là cậu ta phải chọn một thứ tự giải quyết các bài toán sao cho tổng thời gian penalty là thấp nhất. Tổng thời gian penalty trong kì thi ACM được tính như sau: nếu trước khi giải được bài thứ i, tổng thời gian penalty là X và bài thứ i được giải vào thời điểm Y tính từ lúc bắt đầu kì thi thì tổng thời gian penalty sau khi giải được bài thứ i là (X + Y). Tuy rất giỏi trong việc giải quyết các bài toán nhưng việc chọn được thứ tự giải quyết các bài toán sao cho tối ưu thì An lại không thể tính toán được (trớ trêu thật). Là một đồng đội của An, bạn hãy giúp cậu ta chọn được thứ tự tốt nhất để team của mình có thể đạt được thứ hạng cao nhất nhé.

Dữ liệu nhập: dòng đầu tiên chứa một số nguyên dương N - số lượng bài tập của kì thi (1 ≤ N ≤ 105). Dòng thứ 2 chứa N số nguyên dương Ai - thời gian cần để An giải quyết bài toán thứ i (1 Ai ≤ 109).

Dữ liệu xuất: một số nguyên duy nhất là tổng thời gian nhỏ nhất cần tìm.

Ví dụ

  • input
    2
    4 2
    output
    8

 - Làm theo thứ tự 1 - 2: thời điểm giải xong bài đầu tiên là 4, thời điểm giải xong bài thứ 2 là 6 (giải từ phút thứ 5 và giải xong trong 2 phút), tổng thời gian là  4 + 6 =10

 - Làm theo thứ tự 2 - 1: thời điểm giải xong bài đầu tiên là 2, thời điểm giải xong bài thứ 2 là 6, tổng thời gian là 2 + 6 = 8

Vậy tổng thời gian nhỏ nhất là 8

Back to Top