1691C.md (1873B)
1 Source: https://codeforces.com/problemset/problem/1691/C 2 3 C. Sum of Substrings 4 5 time limit per test 6 7 1 second 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 binary string $s$ of length $n$. 22 23 Let's define $d_i$ as the number whose decimal representation is $s_i s_{i+1}$ (possibly, with a leading zero). We define $f(s)$ to be the sum of all the valid $d_i$. In other words, $f(s) = \sum\limits_{i=1}^{n-1} d_i$. 24 25 For example, for the string $s = 1011$: 26 27 * $d_1 = 10$ (ten); 28 * $d_2 = 01$ (one) 29 * $d_3 = 11$ (eleven); 30 * $f(s) = 10 + 01 + 11 = 22$. 31 32 In one operation you can swap any two adjacent elements of the string. Find the minimum value of $f(s)$ that can be achieved if at most $k$ operations are allowed. 33 34 Input 35 36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows. 37 38 First line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $0 \le k \le 10^9$) — the length of the string and the maximum number of operations allowed. 39 40 The second line of each test case contains the binary string $s$ of length $n$, consisting of only zeros and ones. 41 42 It is also given that sum of $n$ over all the test cases doesn't exceed $10^5$. 43 44 Output 45 46 For each test case, print the minimum value of $f(s)$ you can obtain with at most $k$ operations. 47 48 Example 49 50 Input 51 52 ``` 53 3 54 55 4 0 56 57 1010 58 59 7 1 60 61 0010100 62 63 5 2 64 65 00110 66 ``` 67 68 Output 69 70 ``` 71 21 72 22 73 12 74 ``` 75 76 Note 77 78 * For the first example, you can't do any operation so the optimal string is $s$ itself. $f(s) = f(1010) = 10 + 01 + 10 = 21$. 79 * For the second example, one of the optimal strings you can obtain is "0011000". The string has an $f$ value of $22$. 80 * For the third example, one of the optimal strings you can obtain is "00011". The string has an $f$ value of $12$.