#1315. STATUES - Bán tượng

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: Bài tập thầy Vũ Mạnh Hà - Ôn Hải Phòng 08/11/2020

Bờm phát hiện một hang ngầm chứa 𝑁 bức tượng cổ. Các bức tượng cổ khá lớn nên chỉ có thể lấy ra lần lượt từ hai cửa hang ngầm ở hai đầu. Theo đánh giá của các chuyên gia, bức tượng thứ 𝑖 từ trái sang có giá trị 𝑣_𝑖 .

Bờm rao bán 𝑁 bức tượng theo quy cách: mỗi lần bán một bức tượng (lấy ra từ một trong hai đầu của hang ngầm), bức tượng thứ 𝑖 nếu bán ở lượt thứ 𝑗 sẽ có giá 𝑣_𝑖 × 𝑗 .

Hãy xác định tổng thu lớn nhất nếu Bờm bán 𝑁 bức tượng theo cách tối ưu.

Dữ liệu vào:

  • Dòng đầu chứa số nguyên 𝑁\ (1 ≤ 𝑁 ≤ 2000) ;
  • N dòng tiếp theo chứa 𝑁 số nguyên 𝑣_1, 𝑣_2, … , 𝑣_𝑁\ (1 ≤ 𝑣_𝑖 ≤ 1000, ∀𝑖) .

Dữ liệu ra:

  • Một số nguyên là tổng thu lớn nhất.

Ví dụ:

Dữ liệu vào:

5
1
3
1
5
2

Dữ liệu ra:

43