GAME2 - Trò chơi của Bờm

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hieu Nguyen
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Trên mỗi một trong số ~n~ quân bài có ghi một số nguyên dương nhỏ hơn 1000. Các quân bài được xếp thành một dãy, quân nọ nối tiếp quân kia. Bờm vừa phát minh ra một trò chơi mới. Trò chơi đòi hỏi thực hiện một số bước. Tại mỗi bước phải loại bỏ một trong các quân bài trong dãy, không được phép loại quân bài đầu tiên cũng như quân bài cuối cùng. Đối với mỗi quân bài bị loại bỏ sẽ nhận được số điểm bằng tích của số ghi trên quân bài này với tổng các số ghi trên hai quân bài xếp cạnh nó. Trò chơi kết thúc khi dãy chỉ còn hai quân bài đầu tiên và cuối cùng.

Yêu cầu: Hãy tìm số lượng điểm lớn nhất có thể đạt được từ trò chơi mà Bờm vừa phát hành.

Input

  • Dòng đầu tiên chứa số nguyên ~n (3 ≤ n ≤ 700)~.
  • Dòng tiếp theo chứa ~n~ số nguyên là các số viết trên các quân bài được liệt kê theo thứ tự chúng xuất hiện trên dãy quân bài.

Output

  • Ghi ra một số nguyên là số lượng điểm lớn nhất tìm được

Sample

Input #1
4
4 5 6 2
Output #1
86

Problem source: Kc97ble - Free Contest 18

Bình luận

Hãy đọc nội quy trước khi bình luận.