Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11TEST - Kiểm tra năng lực

Để phát triển ngành công nghệ thông tin của vương quốc C11, virtuspro94 đang lên kế hoạch tuyển chọn lại đội ngũ lập trình viên tài năng. Và lần này, anh đã quyết định đưa ra một bài toán khó để kiểm tra năng lực các coders ở vương quốc của mình. Bài toán được virtuspro94 đưa ra như sau :

Cho dãy N số nguyên có giá trị thuộc khoảng [-106, 106]. Bạn được phép chọn một bảng ô vuông bất kì thỏa mãn :

  • H x W = N (với H là chiều cao của bảng và W là chiều rộng của bảng)
  • Min(H, W) >= 2

Với bảng bạn đã chọn, lần lượt điền các số A1, A2, .. , AN từ trái sang phải, trên xuống dưới, nói cách khác các số A1, A2, .. , AN lần lượt được điền vào các ô (1, 1), (1, 2), .. , (1, W), (2, 1), (2, 2), … , (2, W), … , (H, 1), (H, 2), … (H, W). Tiếp đó, bạn sẽ chọn một số ô trong bảng và điểm bạn nhận được chính là tổng các số trên tất cả các ô bạn chọn. Nhưng nếu chỉ có thế thì thực sự quá dễ dàng với trình độ các coders của C11 để đạt được số điểm tốt nhất, nên virtuspro94 đã đưa ra 1 điều kiện oái oăm :

  • Với mọi hình vuông 2 x 2, bạn phải chọn ít nhất 1 ô nhưng đồng thời cũng không được chọn hết cả 4 ô.

Bài toán giờ đã trở nên khá là “dị”. Nhưng bạn là một coder giỏi, hãy thể hiện khả năng của mình bằng việc tìm ra số điểm lớn nhất bạn có thể đạt được là bao nhiêu?

Input

  • Dòng đầu là số N <= 200 và thỏa mãn có ít nhất 1 bảng ô vuông thỏa mãn điều kiện đề bài.
  • Dòng tiếp theo là dãy N số, mỗi số cách nhau 1 dấu cách.

Output

  • 1 dòng duy nhất là số điểm lớn nhất bạn có thể đạt được.

Example

Input:
4
2 3 -1 2
Output:
7

Được gửi lên bởi:Hacker7
Ngày:2012-12-07
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2016-11-02 16:46:34
Code pascal:
http://shink.in/Ebu3h
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.