8.22 猿辅导

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1000005];
int main()
{
    scanf("%d", &n);
    for(int i = 0 ; i < n ; i++){
        scanf("%d",&a[i]);
    }
    int id = 0;
    vector<vector<int>> tree;
    vector<vector<bool>> vis;
    for(int i = 0 ; id < n ; i++){
        vector<int> t;
        vector<bool> v;
        for(int j = 0 ; j < (1<<i) && id < n ; j++){
            t.push_back(a[id++]);
            v.push_back(0);
        }
        tree.push_back(t);
        vis.push_back(v);
    }
    int h = tree.size();
    vector<int> ans;
    for(int i = 0 ; i < h ; i++){
        if(vis[i][0]) continue;
        vis[i][0] = true;
        ans.push_back(tree[i][0]);
    }
    for(int i = 0 ; i < tree[h-1].size() ; i++){
        if(vis[h-1][i]) continue;
        vis[h-1][i] = true;
        ans.push_back(tree[h-1][i]);
    }
    if(tree[h-1].size() != 1<<(h-1)){
        for(int i = (tree[h-1].size() + 1)/2 ; i < tree[h-2].size() ; i++){
            if(vis[h-2][i]) continue;
            vis[h-2][i] = true;
            ans.push_back(tree[h-2][i]);
        }
    }
    for(int i = h-1; i > 0 ; i--){
        int l = tree[i].size();
        if(vis[i][l-1]) continue;
        vis[i][l-1] = true;
        ans.push_back(tree[i][l-1]);
    }
    for(int i = 0 ; i < ans.size() ; i++)
        printf("%d%c", ans[i], i==ans.size()-1?'\n':' ');
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, m;
typedef long long ll ;
ll a[105][2005];
ll sum[105][2005];
ll res[2005];
ll f(){
    ll mmax = res[0];
    ll t[m];
    memset(t, 0, sizeof(t));
    t[0] = res[0];
    for(int i = 1 ; i < m ; i++){
        t[i] = res[i];
        if(t[i-1] > 0)
            t[i] += t[i-1];
        mmax = max(mmax, t[i]);
    }
    return mmax;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            scanf("%lld", &a[i][j]);
        }
        for(int j = m ; j < m+m ; j++){
            a[i][j] = a[i][j-m];
        }
    }
    m*=2;
    for(int j = 0 ; j < m ; j++)
        sum[0][j] = a[0][j];
    for(int i = 1 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            sum[i][j] = sum[i-1][j] + a[i][j];
        }
    }
    ll ans = a[0][0];
    for(int i = 0 ; i < n ; i++){
        for(int j = i ; j < n ; j++){
            memset(res, 0, sizeof(res));
            for(int k = 0 ; k < m ; k++){
                if(i==0)
                    res[k] = sum[j][k];
                else
                    res[k] = sum[j][k] - sum[i-1][k];
            }
            ll t = f();
            ans = max(ans, t);
        }
    }
    printf("%lld\n", ans);
    return 0;
}