#include using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b>s; reverse(ALL(s)); s.push_back('0'); int n=(int)s.size(); int nxt[n];//nxt0 nxt[n-1]=n-1; for(int i=n-2;i>=0;i--){ nxt[i]=nxt[i+1]; if(s[i]=='0') nxt[i]=i; } ll dp1[n+1],dp2[n+1]; rep(i,n+1)dp1[i]=LINF,dp2[i]=LINF; dp1[0]=0,dp2[0]=0; rep(i,n){ if(s[i]=='0'){ chmin(dp1[i+1],dp1[i]); chmin(dp1[i+1],dp2[i+1]+1); chmin(dp2[i+1],dp2[i]+1); }else{ chmin(dp2[nxt[i]+1],dp1[i]+1); chmin(dp2[nxt[i]+1],dp2[i]+1); chmin(dp1[i+1],dp1[i]+1); } } // cout<<" ";for(auto c:s) cout<