CT29043

The ribbons Repaid Streak Puzzle

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Sarla inherited the foundry at the forest village of Briarthorn along with its curious bookkeeping system for ribbons. Time to make sense of it. Task: A binary array may flip at most k zeros to ones. Print the longest run of ones achievable. Input format: First line: n and k. Second line: n values 0/1. Output format: Print the maximum run length. Constraints: 1 <= n <= 4000; 0 <= k <= n; a[i] in {0,1}.

Example 1:

Input: 174 93 1 0 1 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1
Output: 174

Example 2:

Input: 858 683 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 …
Output: 858

Example 3:

Input: 1247 411 1 0 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 1 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1…
Output: 838

Constraints:

1 <= n <= 4000; 0 <= k <= n; a[i] in {0,1}.

Loading...
Test Cases:No test cases
No test cases available.
The ribbons Repaid Streak Puzzle - MEDIUM Coding Problem | CodeTikki