nikcodes's blog

By nikcodes, history, 7 weeks ago, In English

There are N check-post that are placed one after the another in a row. Initially, all the posts are empty. You are given a number K, denoting the awareness of the policemen. If a policeman is placed at a checkpoint X, then he can watch over all the check-posts between the number, max(1, N-K) and min(N, X+K). There are two types of check-posts designated a Type 0 and Type 1 respectively. These check-posts can be described as follows: A type 0 check-post is a closed checkpoint i.e if a policeman is here then he cannot see anything and can only watch over this checkpoint. A type 1 check-post is an open check-post i.e policemen can watch over check-post which are between max(1, N-K) and min(N, X+K).

The cost of putting policemen at i(th) check-post is i. You want to place policemen such that every check-post is being watched. Your task is to find the minimum cost to put the policemen such that all checkpoints are being watched.

Constraints: 1<=N<=100000

INPUT: You will be given N than K and then N values denoting the types of check-post. OUTPUT: A number denoting minimum cost.

TEST CASE input: 5 2 0 0 0 0 0 output: 15
Explanation: placed at 1,2,3,4,5 (1+2+3+4+5)

input: 5 2 0 1 0 1 0

output: 6

Explanation: placed at 2,4 6 (2+4)

input: 5 2 1 1 1 1 1

output: 4

Explanation: placed at 1,3 4(1+3)

  • Vote: I like it
  • -2
  • Vote: I do not like it