把序列分为一些段，每一段形如开头一个 0 后面一堆 1。然后生成一个新数组，新数组中的每个数都由其中的一段缩成，值为其中 1 的个数。例如样例 1 被缩为：1 0 0 1 0 2 0 1 5。

在新数组中，原来的一次操作表现为，选定相邻的三个数，满足中间一个数是 1，右边一个数非 0，然后把右边的数减一加到左边的数上。

此时我们先贪心地做这样的的操作：选择一个大于 1 的数，满足其左边有 $x$ （$x$ 是奇数）个 1，并且再左边一个数是 0。我们把这个数减一，通过 $(x+1)/2$ 次操作移动到左边的 0 上，容易发现这样的操作是不劣的。我们不断做这样的操作直到无法进行。

此时可以从右往左 DP：我们每个时刻当前的状态有两种，一堆连续的大于 1 的数，称为状态 A；或者连续的 $x$ （$x$ 是偶数）个 1，称为状态 B。（为什么是偶数？因为连续的 $x$ 个 1 可以通过 $x/2$ 次操作向前移动一格，我们实际上是持有一段向前移动的 1。）。我们分讨一下转移：

• 如果状态 A 前面是一个 0，明显就无法往前走了，我们抛弃这个状态中的所有元素。
• 如果状态 A 前面遇到了一个大于 1 的数，我们就合并这个大于 1 的数进入当前状态。

• 如果状态 A 遇到了一段 1：

  • 如果这一段 1 左边是一个大于 1 的数，那么我们就不断把状态 A 向左移动直到与其合并，在此过程中右边会多出来一段 1，我们贪心地把他们向左做合并即可。
  • 如果这一段 1 左边是一个 0，那么 1 的个数就一定是偶数（因为我们做了第一步操作），所以此时有两种可能：
    • 将状态 A 移动到这一段 1 最左端，并舍弃这个状态。
    • 直接舍弃当前的状态，将这一段 1 视为一个状态 B。 仔细思考可以发现，这两种策略都不一定劣。所以我们把一个状态同时分裂为这两种状态往后转移。至于复杂度为什么是对的，因为这两个状态砸到下一个大于 1 的数之后又会坍缩为同一个状态，而在此之前他们都不会分裂。所以每个时刻还是只有 $O(1)$ 个状态。

• 如果状态 B 前面遇到一段 1，那么我们直接将他们合并为一段更长的状态 B。

• 如果状态 B 前面遇到一个大于 1 的数，我们就把这些 1 贪心地合并进去。

直接按照这样暴力地 DP 即可。复杂度 $O(n)$。

注意最终状态中可能还有一段连续的 1 未操作，我们处理一下即可。

DP 之前预处理一下一段连续的 1 合并进一个大于 1 的数的结果。注意数组最左端类比于一个大于 1 的数。

代码（较丑）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
string s;
int a[5000009],n,f[5000009];
vector<array<int,4> > mov;
inline bool operator<=(array<int,4> x,array<int,4> y){
    if(x[1]==y[1]&&x[2]==y[2]&&x[3]==y[3]&&x[0]<=y[0])return true;
    return false;
}
void shuf(){
    sort(mov.begin(),mov.end());
    mov.resize(unique(mov.begin(),mov.end())-mov.begin());
    vector<array<int,4> > res={};
    for(auto p:mov){
        while(!res.empty()&&res.back()<=p)res.pop_back();
        res.push_back(p);
    }
    mov=res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>s;
    int lst=-0x3f3f3f3f;
    for(char c:s)if(c=='0'){
        if(lst>=0)a[++n]=lst;
        lst=0;
    }else lst++;
    if(lst>=0)a[++n]=lst;
    for(int i=2;i<=n;i++)f[i]=(i&1?f[i-1]:f[i-1]+(i>>1));
    int trn=0;
    vector<int> stk={};
    for(int i=n;i;i--){
        if(a[i]>1){for(int op=0;op<a[i]-1;op++)stk.push_back(i);}
        else if(!a[i])stk.clear();
        else if(a[i]==1&&!a[i-1]&&i>1&&!stk.empty()){
            int x=stk.back();
            if(x-i&1){
                stk.pop_back();
                a[i-1]=1;
                a[x]--;
                trn+=(x-i+1>>1);
            }
        }
    }
    mov.push_back({0,0,n+1,0});
    // for(int i=1;i<=n;i++)cout<<a[i]<<' ';cout<<endl;
    for(int i=n;i;i--){
        if(a[i]>1){
            for(auto &p:mov){
                p[0]+=(p[2]-i-1)*(p[3]>>1)+f[p[3]];
                p[1]+=a[i]-1;
                p[1]+=(p[3]>>1);
                p[2]=n+1,p[3]=0;
            }
            shuf();
        }else if(a[i]==1){
            int j=i;
            while(a[j-1]==1)j--;
            if(j>1&&!a[j-1]){
                vector<array<int,4> > tmp={};
                for(auto p:mov){
                    if(p[1]){
                        if(!p[1])tmp.push_back({p[0],0,j,i+1-j+1});
                        else{
                            tmp.push_back({p[0]+p[1]*(i-j+1>>1)+f[i-j+1],p[1]+(i-j+1>>1),n+1,0});
                            tmp.push_back({p[0],0,j,i-j+1});
                        }
                        if(tmp.back()[3]&1)tmp.back()[3]--;
                    }else{
                        tmp.push_back({p[0]+(p[2]-i-1)*(p[3]>>1),0,j,(i-j+1)+p[3]});
                        if(tmp.back()[3]&1)tmp.back()[3]--;
                    }
                }
                mov=tmp;
                shuf();
            }else{
                for(auto &p:mov){
                    if(p[1]){
                        int nj=j;
                        if(i-nj+1&1)nj--;
                        assert(!p[3]);
                        p[0]+=p[1]*(i-nj+1>>1)+f[i-nj+1];
                        p[1]+=(i-nj+1>>1);
                        p[2]=n+1,p[3]=0;
                    }else{
                        p[0]+=(p[2]-i-1)*(p[3]>>1);
                        p[1]=0;
                        p[2]=j;p[3]+=(i-j+1);
                        if(p[3]&1)p[3]--;
                    }
                }
                shuf();
            }
            i=j;
        }else if(!a[i]){
            for(auto &p:mov)p[1]=0;
            shuf();
        }
        // cout<<i<<' '<<a[i]<<endl;
        // for(auto p:mov)cout<<p[0]<<' '<<p[1]<<' '<<p[2]<<' '<<p[3]<<endl;
    }
    int mx=0;
    for(auto p:mov)mx=max(mx,p[0]+(p[2]-1)*(p[3]>>1)+f[p[3]]);
    cout<<mx+trn<<endl;
    return 0;
}