Dãy số (THTB Vòng Khu vực 2021)

View as PDF

Points: 200 (p) Time limit: 1.0s Memory limit: 1G Input: stdin Output: stdout

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 1
Output
13

Comments


  • 0
    mcsmuscle    11:48 p.m. 25 jan, 2022

    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


    • 1
      VoBaThongL921    8:48 a.m. 6 nov, 2021

      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ì ...


      • 0
        trieunguyen_a1    5:27 p.m. 31 oct, 2021

        how to n = 6 mà có 7 a[i] ????


        • 0
          anh03032007    11:46 p.m. 7 oct, 2021

          đề này 7-8-9 thi đều được hết hả mọi người


          • 0
            BlockyBlock    9:14 p.m. 6 oct, 2021

            Ey quên đổi int thành long long, pay 80% test 🙂

            1 reply

            • 1
              LeNam2021    7:36 p.m. 5 oct, 2021

              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.


              • 2
                dang7rickroll    7:32 a.m. 5 oct, 2021

                \(Test\) mẫu ghi \(N = 6\), mà ở dưới lại \(7\) phần tử ?

                2 replies

                • 0
                  VoBaThongL921    9:57 p.m. 4 oct, 2021

                  Sao test mẫu n = 6 mà dòng dưới có 7 số vậy ạ ?

                  2 replies

                  • -5
                    minhtuanitk20    9:33 p.m. 4 oct, 2021

                    This comment is hidden due to too much negative feedback. Click here to view it.