VOI 20 Bài 1 - Phần thưởng

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 0.45s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đọc đề gốc tại đây.

Alice vừa đoạt giải quán quân trong một kỳ thi lập trình danh giá. Ban tổ chức trao thưởng thông qua một trò chơi như sau. Có ~n~ thẻ xếp trên một hàng dài, trên mỗi thẻ viết một số nguyên dương. Ban tổ chức cho phép Alice thực hiện nhiều bước để chọn ra đúng ~k~ cặp thẻ, mỗi bước thực hiện theo một trong các quy tắc sau:

  1. Chọn ~2~ thẻ đầu hàng;
  2. Chọn ~2~ thẻ cuối hàng;
  3. Chọn ~1~ thẻ đầu hàng và ~1~ thẻ cuối hàng;
  4. Loại ~1~ thẻ đầu hàng ra khỏi hàng;
  5. Loại ~1~ thẻ cuối hàng ra khỏi hàng.

Sau mỗi bước nếu chọn được ~2~ thẻ thì loại ~2~ thẻ đó ra khỏi hàng và Alice nhận được số tiền thưởng bằng giá trị tuyệt đối của hiệu hai số ghi trên hai thẻ đó.

Yêu cầu: Hãy giúp Alice tìm cách chơi chọn đúng ~k~ cặp thẻ để đạt được tổng số tiền thưởng là lớn nhất.

Input

  • Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~k~ ~(2 \times k \leq n)~;
  • Dòng thứ hai chứa ~n~ số nguyên dương là giá trị ghi trên từng thẻ, mỗi thẻ một số tương ứng lần lượt từ đầu hàng. Các số có giá trị không vượt quá ~10^9~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên duy nhất là tổng tiền thưởng lớn nhất tìm được.

Giới hạn

  • Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 300~, ~k \leq 2~;
  • ~40\%~ số test khác ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 30~, ~2 \times k = n~;
  • ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 300~.

Sample Input

6 2
1 3 10 2 1 4

Sample Output

12

Note

Giải thích test ví dụ

  • Bước ~1~: Alice chọn hai thẻ cuối hàng là ~1~ và ~4~ và nhận được số tiền thưởng là ~|4 - 1| = 3~;
  • Bước ~2~: Alice loại thẻ cuối hàng có giá trị ~2~;
  • Bước ~3~: Alice chọn một thẻ đầu hàng và một thẻ cuối hàng là ~1~ và ~10~ và nhận được số tiền thưởng là ~|10 - 1| = 9~;

Tổng tiền thưởng Alice nhận được là ~3 + 9 = 12~.

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.


There are no comments at the moment.