Dãy số (THTB Vòng Khu vực 2021)
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Bob gửi cho Alice một dãy số nguyên gồm \(N\) phần tử: \(A_1,A_2,...,A_N\) đây là thông tin về một kho báu. Một đoạn con \((L,R)\) của dãy là một dãy gồm các phần tử liên tiếp \(A_L,A_{L+1},...,A_R\) với \(1\leq L<R\leq N\), đoạn con \((L,R)\) được gọi là chứa thông tin quan trọng nhất nếu:
- Phần tử đầu tiên bằng phần tử cuối cùng (\(A_L=A_R\)).
- Tổng các phần tử của đoạn là lớn nhất có thể.
Yêu cầu: Hãy giúp Alice tìm đoạn con chứa thông tin quan trọng nhất.
Input
- Dòng thứ nhất chứa số nguyên dương \(N\).
- Dòng thứ hai chứa số nguyên \(A_1,A_2,...,A_N\text{ }(|A_i|\leq 10^9,1\leq i\leq N)\).
Output
- Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng của đoạn con chứa thông tin quan trọng nhất.
Constraints
- \(N\leq 10^5\)
Scoring
- Subtask \(1\) (\(40\%\) số điểm): \(N\leq 10^2\)
- Subtask \(2\) (\(30\%\) số điểm): \(N\leq 10^3\)
- Subtask \(3\) (\(30\%\) số điểm): \(N\leq 10^5\)
Example
Test 1
Input
7
3 3 3 3 1 11 1Output
13
Bình luận
e viết bằng py, 2 test cuối 11 và 12 của e lỗi 'IndexError', xem test cũng như ko, nhờ mọi người xem fix giúp ạ CODE python
ghét mấy ông chép code y hệt trong editorial luôn ạ, không thèm thay tên biến gì luôn. Bí quá thì tham khảo chứ Ctrl C + ctrl V thì ...
how to n = 6 mà có 7 a[i] ????
đề này 7-8-9 thi đều được hết hả mọi người
Ey quên đổi int thành long long, pay 80% test 🙂
Scratch với Time limit 1.0s chạy không kịp các test cuối. Xin Admin nâng Time cho Scratch.
\(Test\) mẫu ghi \(N = 6\), mà ở dưới lại \(7\) phần tử ?
Sao test mẫu n = 6 mà dòng dưới có 7 số vậy ạ ?
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.