codeforces-scrape

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

1114B.md (2689B)


      1 Source: https://codeforces.com/problemset/problem/1114/B
      2 
      3 B. Yet Another Array Partitioning Task
      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 An array $b$ is called to be a subarray of $a$ if it forms a continuous subsequence of $a$, that is, if it is equal to $a_l$, $a_{l + 1}$, $\ldots$, $a_r$ for some $l, r$.
     22 
     23 Suppose $m$ is some known constant. For any array, having $m$ or more elements, let's define it's beauty as the sum of $m$ largest elements of that array. For example:
     24 
     25 * For array $x = [4, 3, 1, 5, 2]$ and $m = 3$, the $3$ largest elements of $x$ are $5$, $4$ and $3$, so the beauty of $x$ is $5 + 4 + 3 = 12$.
     26 * For array $x = [10, 10, 10]$ and $m = 2$, the beauty of $x$ is $10 + 10 = 20$.
     27 
     28 You are given an array $a_1, a_2, \ldots, a_n$, the value of the said constant $m$ and an integer $k$. Your need to split the array $a$ into exactly $k$ subarrays such that:
     29 
     30 * Each element from $a$ belongs to exactly one subarray.
     31 * Each subarray has at least $m$ elements.
     32 * The sum of all beauties of $k$ subarrays is maximum possible.
     33 
     34 Input
     35 
     36 The first line contains three integers $n$, $m$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m$, $2 \le k$, $m \cdot k \le n$) — the number of elements in $a$, the constant $m$ in the definition of beauty and the number of subarrays to split to.
     37 
     38 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).
     39 
     40 Output
     41 
     42 In the first line, print the maximum possible sum of the beauties of the subarrays in the optimal partition.
     43 
     44 In the second line, print $k-1$ integers $p_1, p_2, \ldots, p_{k-1}$ ($1 \le p_1 \lt p_2 \lt \ldots \lt p_{k-1} \lt n$) representing the partition of the array, in which:
     45 
     46 * All elements with indices from $1$ to $p_1$ belong to the first subarray.
     47 * All elements with indices from $p_1 + 1$ to $p_2$ belong to the second subarray.
     48 * $\ldots$.
     49 * All elements with indices from $p_{k-1} + 1$ to $n$ belong to the last, $k$-th subarray.
     50 
     51 If there are several optimal partitions, print any of them.
     52 
     53 Examples
     54 
     55 Input
     56 
     57 ```
     58 9 2 3
     59 5 2 5 2 4 1 1 3 2
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 21
     66 3 5
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 6 1 4
     73 4 1 3 2 2 3
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 12
     80 1 3 5
     81 ```
     82 
     83 Input
     84 
     85 ```
     86 2 1 2
     87 -1000000000 1000000000
     88 ```
     89 
     90 Output
     91 
     92 ```
     93 0
     94 1
     95 ```
     96 
     97 Note
     98 
     99 In the first example, one of the optimal partitions is $[5, 2, 5]$, $[2, 4]$, $[1, 1, 3, 2]$.
    100 
    101 * The beauty of the subarray $[5, 2, 5]$ is $5 + 5 = 10$.
    102 * The beauty of the subarray $[2, 4]$ is $2 + 4 = 6$.
    103 * The beauty of the subarray $[1, 1, 3, 2]$ is $3 + 2 = 5$.
    104 
    105 The sum of their beauties is $10 + 6 + 5 = 21$.
    106 
    107 In the second example, one optimal partition is $[4]$, $[1, 3]$, $[2, 2]$, $[3]$.