codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1197C.md (1583B)


      1 Source: https://codeforces.com/problemset/problem/1197/C
      2 
      3 C. Array Splitting
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a sorted array $a_1, a_2, \dots, a_n$ (for each index $i \gt 1$ condition $a_i \ge a_{i-1}$ holds) and an integer $k$.
     22 
     23 You are asked to divide this array into $k$ non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray.
     24 
     25 Let $max(i)$ be equal to the maximum in the $i$-th subarray, and $min(i)$ be equal to the minimum in the $i$-th subarray. The cost of division is equal to $\sum\limits_{i=1}^{k} (max(i) - min(i))$. For example, if $a = [2, 4, 5, 5, 8, 11, 19]$ and we divide it into $3$ subarrays in the following way: $[2, 4], [5, 5], [8, 11, 19]$, then the cost of division is equal to $(4 - 2) + (5 - 5) + (19 - 8) = 13$.
     26 
     27 Calculate the minimum cost you can obtain by dividing the array $a$ into $k$ non-empty consecutive subarrays.
     28 
     29 Input
     30 
     31 The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$).
     32 
     33 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($ 1 \le a_i \le 10^9$, $a_i \ge a_{i-1}$).
     34 
     35 Output
     36 
     37 Print the minimum cost you can obtain by dividing the array $a$ into $k$ nonempty consecutive subarrays.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 6 3
     45 4 8 15 16 23 42
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 12
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 4 4
     58 1 3 3 7
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 8 1
     71 1 1 2 3 5 8 13 21
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 20
     78 ```
     79 
     80 Note
     81 
     82 In the first test we can divide array $a$ in the following way: $[4, 8, 15, 16], [23], [42]$.