Truyền Tin - MSGAME (PreVOI Phú Thọ)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2300 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: MSGAME.INP Output: MSGAME.OUT

Có \(n\) người đánh số từ \(1\) đến \(n\) xếp thành một hàng và cùng nhau chơi trò chơi truyền tin. Người thứ \(i\) (\(1 \le i \le n\)) có độ trễ khi truyền tin là \(d_i\). Độ trễ khi người thứ \(i\) truyền tin cho người thứ \(j\) (\(1 \le i \le j \le n\)) được tính bằng

\[D(i,j)=\max\{d_i,d_{i+1},\ldots,d_j\}.\]

Người quản trò muốn tìm ra \(k\) (\(1 \le k \le n\)) người chơi để tổng độ trễ liên lạc là nhỏ nhất. Một cách hình thức, cần chọn \(k\) chỉ số

\[1 \le i_1 < i_2 < \cdots < i_k \le n\]

sao cho

\[w=\sum_{1 \le x \le y \le k}D(i_x,i_y)\]

là nhỏ nhất.

Input

  • Dòng đầu chứa hai số nguyên \(n, k\).
  • Dòng thứ hai chứa \(n\) số nguyên dương \(d_1,d_2,\ldots,d_n\) (\(d_i \le 10^9\)).

Output

  • In ra một số nguyên duy nhất là giá trị nhỏ nhất của \(w\).

Example

Test 1

Input 
4 3
1 2 2 1
Output 
10
Note

Chọn ba người \(1,2,4\). Tổng độ trễ là

\[D(1,2)+D(1,4)+D(2,4)+D(1,1)+D(2,2)+D(4,4)=10.\]

Scoring

  • \(20\%\) số điểm: \(n \le 20\).
  • \(30\%\) số điểm: \(k=3\) và \(n \le 10^4\).
  • \(30\%\) số điểm: \(n \le 500\).
  • \(20\%\) số điểm: \(n \le 10^4\).

Bình luận (1)

Mới nhất
Tải bình luận...

Kỳ thi: