DAYSO2 - Dãy số 2 (OLPCĐ 2014)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Cho dãy số gồm n số nguyên a1, a2, ..., an. Một đoạn con của dãy đã cho là dãy ai,..., aj (1 ≤ i ≤ j ≤ n), dãy có độ dài (j - i + 1) và có trọng số bằng tổng (ai + ... + aj).

Yêu cầu: Tìm đoạn con có độ dài là một số chia hết cho 3 và có trọng số lớn nhất.

Dữ liệu nhập:

- Dòng đầu ghi số nguyên n (3 ≤ n ≤ 100.000).

- Dòng thứ hai ghi n số nguyên a1, a2, ..., an (|ai| < 109).

Dữ liệu xuất:

- Giá trị trọng số của đoạn con tìm dược.

 

Ví dụ

  • input
    11
    1 1 1 -9 1 1 1 1 -1 1 -9
    output
    4
  • input
    3
    1 2 3
    output
    6
  • input
    4
    -1 5 -10 1
    output
    -4
Back to Top