codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

660C.md (1217B)


      1 Source: https://codeforces.com/problemset/problem/660/C
      2 
      3 C. Hard Process
      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 an array *a* with *n* elements. Each element of *a* is either 0 or 1.
     22 
     23 Let's denote the length of the longest subsegment of consecutive elements in *a*, consisting of only numbers one, as *f*(*a*). You can change no more than *k* zeroes to ones to maximize *f*(*a*).
     24 
     25 Input
     26 
     27 The first line contains two integers *n* and *k* (1 ≤ *n* ≤ 3·105, 0 ≤ *k* ≤ *n*) — the number of elements in *a* and the parameter *k*.
     28 
     29 The second line contains *n* integers *a**i* (0 ≤ *a**i* ≤ 1) — the elements of *a*.
     30 
     31 Output
     32 
     33 On the first line print a non-negative integer *z* — the maximal value of *f*(*a*) after no more than *k* changes of zeroes to ones.
     34 
     35 On the second line print *n* integers *a**j* — the elements of the array *a* after the changes.
     36 
     37 If there are multiple answers, you can print any one of them.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 7 1  
     45 1 0 0 1 1 0 1
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 4  
     52 1 0 0 1 1 1 1
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 10 2  
     59 1 0 0 1 0 1 0 1 0 1
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 5  
     66 1 0 0 1 1 1 1 1 0 1
     67 ```