Bedao OI Contest 6 - Lại là một bài toán cực đại hoá

View as PDF
Submit solution
Points: 0.00 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: maximize.inp
Output: maximize.out
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho số nguyên ~N~ và mảng ~a_1, a_2, \ldots, a_n~. Điểm của một đoạn liên tiếp bằng tổng giá trị lớn nhất và giá trị bé nhất trong đoạn. Cắt mảng đã cho thành ~K~ đoạn liên tiếp không giao nhau, không rỗng sao cho tổng điểm của các đoạn là lớn nhất. Mỗi phần tử phải nằm trong chính xác một đoạn.

Input

Dữ liệu vào từ file văn bản maximize.inp.

Dòng đầu tiên gồm số nguyên ~N~ – Số lượng phần tử của mảng (~1 \le N \le 10^5, 1 \le K \le \min(N, 20)~).

Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \ldots, a_n~ – Giá trị của mảng (~0 \le a_i \le 10^9, \forall 1 \le i \le N~).

Output

In ra file văn bản maximize.out một số nguyên duy nhất là kết quả bài toán.

Scoring

Subtask Điểm Giới hạn
1 ~8~ ~K = min(2, n)~
2 ~8~ ~a_1 \le a_2 \le \ldots \le a_n~ hoặc ~a_1 \ge a_2 \ge \ldots \ge a_n~
3 ~18~ ~max_{i=1}^{N} a_i - min_{i=1}^{N} a_i \le 10~
4 ~14~ ~N \le 1000~
5 ~20~ ~N \le 10000~
6 ~32~ Không có ràng buộc gì thêm

Sample Input 1

5 3
3 5 2 3 4

Sample Output 1

22

Sample Input 2

3 2
10 6 2006

Sample Output 2

4028

Notes

Ở ví dụ 1, ta chia thành 3 đoạn ~[1, 1], [2, 2]~ và ~[3, 5]~. Kết quả của cách chia này là ~3 + 3 + 5 + 5 + 2 + 4 = 22~.

Ở ví dụ 2, ta chia thành 2 đoạn ~[1, 2]~ và ~[3, 3]~. Kết quả của cách chia này là ~10 + 6 + 2006 + 2006 = 4028~.

Comments

Please read the guidelines before commenting.