Educational Codeforces Round 11C. Hard Process two pointer

地址：http://codeforces.com/contest/660/problem/C

题目：

You are given an array a with n elements. Each element of a is either 0 or 1.

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).

Input

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.

The second line contains n integers ai (0 ≤ ai ≤ 1) — the elements of a.

Output

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.

On the second line print n integers aj — the elements of the array a after the changes.

If there are multiple answers, you can print any one of them.

Examples

input

7 1
1 0 0 1 1 0 1

output

4
1 0 0 1 1 1 1

input

10 2
1 0 0 1 0 1 0 1 0 1

output

5
1 0 0 1 1 1 1 1 0 1

思路：一开始我用的是n^2的算法，一直tle，后来才知道有种算法叫尺取法：就是动态维护一个长度为x的区间，并同时记录起始位置和终点位置。

　　对这题而言，就是维护含0数为k的0,1区间，记录长度最大值，和起始位置和终点位置;

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <queue>

 #include <stack>

 #include <map>

 #include <vector>

 #define PI acos((double)-1)

 #define E exp(double(1))

 using namespace std;

 int a[];

 int main (void)

 {

     int n,k,s=,e=,sum=,len=;

     cin>>n>>k;

     for(int i = ; i<=n; i++)

         {

             scanf("%d",&a[i]);

             sum += (a[i] == );

             while(sum > k)

                 {

                     sum -= (a[++s] == );

                 }

             if(len < i - s)

                 {

                     e = i;

                     len = i - s;

                 }

         }

     cout<<len<<endl;

     for(int i = ; i<=n; i++)

         if(e>= i && i> e - len )

             {

                     printf("1 ");

             }

         else

             {

                     printf("%d ",a[i]);

             }

     return ;

 }

巴特西

Educational Codeforces Round 11C. Hard Process two pointer

最新文章

热门文章