Problem ID:
pumpkin
Points:
2.6 (partial)
Time limit:
1.25s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem types
Allowed languages
C, C++, Java, Pascal, Perl, Python
Vào ngày Halloween,
muốn trang trí căn phòng của mình bằng một dãy các quả bí ngô. Các quả bí ngô này được đánh số ~1, 2, 3, ... n~. Mỗi quả có một hình thù độc đáo riêng có quả mặt cười, quả khóc, quả giận dữ,... và cần được xếp thành một hàng.
Khi xếp những quả bí ngô này cạnh nhau thành một hàng, chúng sẽ có một độ hấp dẫn nhất định. Những cách xếp khác nhau sẽ có độ hấp dẫn khác nhau.
đã tiến hành đánh giá độ hấp dẫn của cách xếp bằng cách đánh giá từng cặp bí ngô kề nhau: cậu xét một cặp bí ngô ~(i, j)~, độ hấp dẫn của cặp bí ngô này khi đứng liền kề nhau và ~i~ đứng trước ~j~ sẽ là ~a_{ij}~. Như vậy, độ hấp dẫn của một cách xếp sẽ là tổng độ hấp dẫn của tất cả các cặp bí ngô đứng kề nhau. (đọc ví dụ và giải thích để hiểu rõ hơn)Vì muốn căn phòng của mình phải thật hấp dẫn, nên
muốn độ hấp dẫn của cách xếp phải là lớn nhất. Trong lúc còn đang bận cày anime, các bạn hãy giúp cậu ấy tìm giá trị lớn nhất đó nhé.Dữ liệu vào
- Dòng đầu tiên chứa số ~n~ - số lượng quả bí ngô cần sắp xếp.
- ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên ~a_{i1}, a_{i2},..., a_{in}~ ~(|a_{ij}| \le 10^6, a_{ii} = 0)~ - thể hiện độ hấp dẫn của từng cặp bí ngô nếu để kề nhau theo thứ tự ~i \to j~.
Dữ liệu ra
Gồm một dòng duy nhất, ghi giá trị độ hấp dẫn lớn nhất mà
có thể đạt được.Giới hạn
- ~50\%~ số điểm có ~n \le 10~.
- ~50\%~ số điểm còn lại có ~n \le 18~.
Sample Input
5
0 1 5 -3 7
-4 0 2 8 4
7 3 0 -1 9
4 5 -2 0 8
8 -9 -1 -2 0
Sample Output
29
Giải thích
Cách xếp tối ưu là ~2 \to 4 \to 5 \to 1 \to 3~. Độ hấp dẫn của cách xếp này là ~a_{24} + a_{45} + a_{51} + a_{13} = 8+8+8+5 = 29~.
Comments