Nội dung Bài tập
- Mã:
- OLP.DAYSO
- Tên:
- Dãy số (OLP Không chuyên 2014)
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 64 MB
- Được tạo bởi:
- thuthq
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ụ
-
input11
-1 3 -1 -9 -1 1 1 1 1 1 -9 - output5
Giải thích: Hai đoạn có tổng lớn nhất là (-1, 3, -1) và (-1, 1, 1, 1, 1, 1)
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...