#1046 · OLP 2014 - Dãy số

Cho dãy số gồm n số nguyên a_1, a_2, ..., a_n. Một đoạn con của dãy đã cho là dãy a_i,...,a_j (1 \leq i \leq j \leq n), dãy có độ dài (j - i + 1) và có trọng số bằng tổng (a_i + ... + a_j).

Yêu cầu: Tìm hai đoạn con không có phần tử chung, mỗi đoạn có độ dài là một số chia hết cho 3 và tổng trọng số của hai đoạn con là lớn nhất.

Vào từ file văn bản có định dạng như sau:

• Dòng đầu ghi số nguyên n (n \geq 6);
• Dòng thứ hai ghi n số nguyên a_1, a_2, ..., a_n (|a_i| \leq 10^9).

Ghi ra một số là tổng trọng số của hai đoạn con tìm được.