DAYSO7 - Dãy số (OLP Không chuyên 2014)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.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, ai+1, …, aj (1 ≤ i ≤ j ≤ n), dãy có độ dài (j − i + 1) và có trọng số bằng tổng (ai + ai+1 + …+ aj).

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 nhập:

- Dòng thứ nhất là số nguyên n (6 ≤ n ≤ 2 x 105).

- Dòng thứ hai là n số nguyên a1, a2, …, an (|ai| ≤ 109), mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất:

- Là tổng trọng số của hai đoạn con tìm được.

Ví dụ

  • input
    11
    -1 3 -1 -9 -1 1 1 1 1 1 -9
    output
    5

Hai đoạn có tổng lớn nhất là (-1, 3, -1) và (-1, 1, 1, 1, 1, 1)

Back to Top