Codeforces 660C-Hard Process【尺取法经典练习】

本是古典何须时尚 2022-08-21 12:56 170阅读 0赞

C. Hard Process

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 *a**i* (0 ≤ *a**i* ≤ 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 *a**j* — 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

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int num[300000+100];
    int main()
    {
    	int n,k;
    	while(scanf("%d%d",&n,&k)!=EOF)
    	{
    		for(int i=1;i<=n;i++)
    		{
    			scanf("%d",&num[i]);
    		}
    		int r=1,l=1,zr=0,ans=0,ansl=1,ansr=0;
    		while(r<=n)
    		{
    			while(r<=n&&zr<=k)
    			{
    				if(num[r]==0)
    				{
    					if(zr==k)
    					break;
    					else
    					{
    						zr++;
    					}
    				}
    				r++;
    			}
    			if(r-l>ans)
    			{
    				ansr=r-1;
    				ansl=l;
    				ans=r-l;
    			}
    			while(l<=n&&num[l])
    			l++;
    			l++,zr--;
    		}
    		printf("%d\n",ans);
    		for(int i=1;i<=n;i++)
    		{
    			if(i>=ansl&&i<=ansr)
    			printf("1 ");
    			else
    			printf("%d ",num[i]);
    		} 
    		printf("\n");
    	}
    	return 0;
    }