codeforces 660 C. Hard Process (ruler)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年06月08日 星期三 23时43分18秒
  4File Name :code/cf/problem/660C.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=3E5+7;
 34int n,k;
 35int sum[N],a[N];
 36
 37void ruler()
 38{
 39    int head = 1;
 40    int tail = 1;
 41    int l,r;
 42    int  res = -1;
 43    int cnt = 0 ;
 44
 45    while (tail<=n)
 46    {
 47	while (a[tail]==1) tail++;
 48//	cout<<"head:"<<head<<" tail:"<<tail<<endl;
 49	if (a[tail]==0&&tail<=n) cnt++;
 50
 51	while (sum[tail]-sum[head-1]<=k&&tail<=n) tail++;
 52//	cout<<"head:"<<head<<"tail:"<<tail<<endl;
 53	    if (tail-head>res)
 54	    {
 55		res = tail-head;
 56	//	cout<<"res:"<<res<<endl;
 57		l = head;
 58		r = tail-1;
 59	    }
 60
 61	while (head<=tail&&sum[tail]-sum[head-1]>k) head++;
 62//	cout<<"head::"<<head<<" tail:"<<tail<<endl;
 63	if (tail<=n&&tail-head+1>res)
 64	{
 65	    res = tail-head+1;
 66	    l = head;
 67	    r = tail;
 68	}
 69
 70
 71    }
 72
 73
 74    for ( int i = l ; i <= r ; i++) a[i] = 1;
 75
 76    cout<<res<<endl;
 77    for ( int i = 1 ; i <= n ; i++) cout<<a[i]<<" ";
 78}
 79int main()
 80{
 81	#ifndef  ONLINE_JUDGE 
 82	freopen("code/in.txt","r",stdin);
 83  #endif
 84
 85	cin>>n>>k;
 86
 87	sum[0] = 0;
 88	for ( int i = 1; i <= n ; i++)
 89	{
 90	    scanf("%d",&a[i]);
 91	    sum[i] = sum[i-1] +(1-a[i]);
 92	}
 93
 94	ruler();
 95
 96
 97  #ifndef ONLINE_JUDGE  
 98  fclose(stdin);
 99  #endif
100    return 0;
101}