#5085. SEQ - Dãy số

Bộ nhớ: 256 MiB Thời gian: 1000 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

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 ≤ i ≤ j ≤ 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.

Dữ liệu:

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

Kết quả:

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

Ví dụ:

Dữ liệu:

11
-1 3 -1 -9 -1 1 1 1 1 1 -9

Kết quả:

5

Giới hạn:

  • 30\% số test có n ≤ 20 ;
  • 30\% số test có n ≤ 200 ;
  • 20\% số test khác có n ≤ 2000 ;
  • 20\% số test còn lại có n ≤ 200000 .