Points:
1800 (p)
Time limit:
1.5s
Memory limit:
1G
Input:
stdin
Output:
stdout
Do quá chán trong những ngày nghỉ dịch,
và bot đã phải chế những trò chơi mới để chơi. Và đây là một trong số chúng:Bộ bài mà \(n\) thẻ bài, thẻ bài thứ \(i\) có giá trị \(a_i\). Luật chơi như sau:
mới chế gồm có- Các thẻ bài sẽ được đặt trên một hàng trước mặt họ từ \(1\) đến \(n\).
- Đầu tiên, \([l,r]\) \((l\leq r)\). sẽ được lấy tất cả các thẻ bài trong đoạn \([l,r]\). sẽ chọn một cặp số
- Tiếp theo, bot \(j\) bất kỳ \((l\leq j\leq r)\). sẽ được lấy thẻ bài có số hiệu \(j\). sẽ phải chọn một số
- Kết quả của trò chơi sẽ là tổng giá trị của tất cả các thẻ bài còn lại mà đã lấy.
- Trường hợp \(l=r\) ( chỉ lấy một lá) thì kết quả của trò chơi sẽ là \(0\) do chỉ có thể lấy 1 lá duy nhất.
sẽ cố để tối đa hóa số điểm, trong khi đó bot sẽ cố để giảm thiểu số điểm.
muốn biết cách để đạt điểm tối đa nhưng mà do làm ra quá nhiều thẻ nên không biết phải lấy như thế nào. Các bạn hãy giúp nhé!
Input
- Dòng đầu tiên nhập số \(n\) cho biết số lượng thẻ bài.
- Dòng tiếp theo nhập \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) cho biết giá trị của các thẻ bài.
Output
- Duy nhất một số là số điểm tối đa có thể đạt được.
Constraints
- \(1\leq n\leq 10^6\)
- \(-30\leq a_i\leq 30\)
Scoring
- Subtask #1 (\(30\%\) số điểm): \(n\leq 10^3\).
- Subtask #2 (\(20\%\) số điểm): \(a_i\geq 0\).
- Subtask #3 (\(50\%\) số điểm): Không có ràng buộc gì thêm.
Example
Sample input 1
5
5 -2 10 -1 4
Sample output 1
6
Sample input 2
3
-10 6 -15
Sample output 2
0
Note
- Trong ví du 1, \(5\) thẻ trong bộ bài, bot sẽ lấy thẻ số \(3\) để được số điểm tối đa là \(5+(-2)+(-1)+4=6\). sẽ lấy hết
- Trong ví dụ 2, \(1\) thẻ bất kỳ trong bộ bài, bot phải lấy thẻ duy nhất đó để được số điểm tối đa là \(0\). Trường hợp lấy nhiều hơn \(1\) thẻ thì số điểm sẽ nhỏ hơn \(0\). có thể lấy duy nhất
Nguồn: Lấy cảm hứng từ cốt phốt. Bài này chỉ là bản khó hơn ở phần dữ liệu thôi hehe
Comments