Triway Cup '19 Summer Junior P2 - Thanos Knows the Most

View as PDF

Submit solution

Points: 5
Time limit: 1.5s
Memory limit: 256M

Author:
Problem type

DISCLAIMER: This problem statement contains NO spoilers to the film Avengers: Endgame and is in no way, shape, or form affiliated to Marvel Entertainment. Uses of characters, settings, and scenes are parodical only.


Thanos wants to balance the universe, but the pesky Avengers keep getting in his way. He's hired you, a computer scientist, to help him obtain the infinity stones. Help him find them, and it will put a smile on his face.

The planets in Thanos' path can be represented with an N-sized array. There are M infinity stones scattered on different planets throughout the universe. Thanos needs to collect all of the infinity stones, but he does not want to spend too much time doing so, as the Avengers are going after him and he wants to settle down on his farm. Every time he collects a stone, he has to stop for 1 minute (to fight some Avengers, sacrifice Gamora, etc.), but he does not need to spend time travelling between planets due to cutting-edge alien technology.

Since many other people have been collecting these stones, many of the stones are near each other. Thanos can use his minions to collect multiple adjacent stones (stones that are next to each other in an array) in one trip.

Calculate the minimum amount of time, in minutes, for Thanos to collect all M infinity stones, and he will hope that they remember you.

Input Specification

The first line of input will contain two space-separated integers: N and M
The next N lines will each contain a single digit: either 0 or 1, representing the number of infinity stones on the i^\text{th} planet.

Constraints

0 < M < N < 10^4

Output Specification

A single integer: the minimum amount of time that Thanos and his minions need to collect all the infinity stones.

Sample Input

10 6
0
1
1
0
1
0
0
1
1
1

Sample Output

3

Explanation

The stones at index 1 and 2 are adjacent, which increments the time by 1. The stone at index 4 is on its own, so Thanos must collect it by itself, incrementing the time by 1 again. The stones at indices 7, 8 and 9 are all adjacent to one another, and so the time increments by only 1. The final total time is 3.


Comments


  • 0
    Dman27  commented on June 24, 2021, 6:51 p.m.

    I was struggling with this problem for a while because by adjacent they mean any amount of adjacent stones in a row, not just adjacent by one planet. 111111 would still count as one minute because all of the stones are considered adjacent.