DMOPC '21 Contest 6 P2 - Gacha Luck

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 3.0s
Memory limit: 1G

Problem type

Your friend has just accused you of having good gacha luck. To prove them wrong, you have been keeping track of the results of every gacha pull over the past few months in a spreadsheet. Specifically, your spreadsheet contains N entries, each containing a value of either a 0 or a 1. A value of 1 in the i-th entry denotes that the i-th pull contained a 4 star card, and a 0 denotes otherwise. The unluckiness score of a subsection (a contiguous subsequence) of these entries is calculated as follows:

  1. The score is initially set to be the number of 0s in the subsection.
  2. Then, for each 1 in the subsection, the unluckiness score is halved without rounding.
  3. Finally, the score is set to be the smallest integer that is no smaller than its current value.

To refute their claim as effectively as possible, you will send them K screenshots containing mutually disjoint subsections of your spreadsheet. What is the maximum possible total unluckiness score of the K subsections in the screenshots?


1 \le K \le N \le 10^6

Subtask 1 [1/15]

K = 1

1 \le N \le 500

Subtask 2 [1/15]

K = 1

1 \le N \le 3 \times 10^3

Subtask 3 [2/15]

K = 1

Subtask 4 [5/15]

1 \le K \le N \le 500

Subtask 5 [3/15]

1 \le K \le N \le 3 \times 10^3

Subtask 6 [3/15]

No additional constraints.

Input Specification

The first line contains 2 integers N and K.

The second line contains a binary string of length N, representing the entries of the spreadsheet in order.

Output Specification

Output a single integer on its own line, the maximum possible total unluckiness score of the K subsections.

Sample Input

9 2

Sample Output



One optimal solution would be to include the first 6 entries in the first screenshot and the 8-th and 9-th entries in the second. These have unluckiness scores of 3 and 2 respectively, giving a total unluckiness score of 5.


  • -2
    iamaperson133769420  commented on March 5, 2022, 5:53 p.m.

    the only thing ik about gacha life is that it exists so i dont understand the problem

    • -1
      Spitfire720  commented on March 5, 2022, 6:13 p.m.

      You don't need background knowledge on Gacha Life to solve it. I would know because I did it.