Bedao Regular Contest 16 - Too Spicy...

View as PDF

Submit solution


Points: 0.80 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trung là một người thích ăn cay vô cùng. Hôm nay cậu đang tham gia thử thách ăn cay siêu khủng khiếp.

Cho ~n~ miếng pizza siêu cay được đặt theo vòng tròn, các miếng pizza được đánh số từ ~0~ đến ~n-1~, miếng thứ ~i~ kề với miếng ~(i + 1) \bmod n~. Miếng thứ ~i~ có độ cay là ~a_i~. Để ăn được miếng pizza này, Trung phải có sức chịu đựng là ~k \ge a_i~. Sau khi ăn xong, sức chịu đựng của Trung sẽ được tăng lên bằng ~k + a_i~.

Hãy giúp Trung tìm sức chịu đựng ban đầu nhỏ nhất có thể để có thể hoàn thành thử thách, biết rằng Trung sẽ được phép ăn miếng pizza đầu tuỳ ý, nhưng sau đó Trung chỉ ăn các miếng mà kề với tối đa một miếng khác.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 5 \times 10^5)~ — số lượng miếng pizza.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^{13})~. Các miếng pizza này được xếp theo vòng tròn.

Output

In ra một số nguyên duy nhất là sức chịu đựng ban đầu nhỏ nhất mà Trung cần có để hoàn thành được thử thách.

Scoring

Subtask Điểm Giới hạn
1 ~20~ ~a_i \le 100, n \le 15~
2 ~30~ ~n\le 1000~
3 ~50~ không có giới hạn gì thêm

Sample Input 1

4
10 20 15 1

Sample Output 1

9

Notes

Với sức chịu đựng ban đầu là ~9~, Trung có thể chọn ăn lần lượt các miếng pizza ~4~, ~1~, ~3~ và ~2~.


Comments

Please read the guidelines before commenting.



  • 0
    ngokhanh  commented on Jan. 18, 2024, 1:38 p.m.

    Bài hàm check n^2 vẫn ăn 96 điểm :))


    • 0
      ba1234anh  commented on Jan. 18, 2024, 2:26 p.m.

      test yếu à


  • 18
    hungntils  commented on Aug. 13, 2023, 12:20 p.m.

    Bài tương tự:

    https://codeforces.com/problemset/problem/1810/E