Submission #2530761

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

using T=vector<ll>;
class SegmentTree{
    int N;
    int M;
    vector<T> dat;
    
    T merge(T& x,T& y){
        T res(x.size());
        for(int i=0;i<x.size();i++){
            res[i]=max(x[i],y[i]);
        }
        return res;
    }
    T query_impl(int a,int b,int k,int l,int r){
        if(a<=l && r<=b) return dat[k];
        if(b<=l || r<=a) return T(M);
        int mid=(l+r)/2;
        T x1=query_impl(a,b,k*2+1,l,mid);
        T x2=query_impl(a,b,k*2+2,mid,r);
        return merge(x1,x2);
    }
    public:
    SegmentTree(int n,int m):M(m){
        N=1;
        while(N<n){
            N*=2;
        }
        dat.assign(2*N-1,T(m,0));
    }
    void update(int pos,T& vec){
        pos+=N-1;
        dat[pos]=vec;
        while(pos){
            int par=(pos-1)/2;
            int c1=par*2+1;
            int c2=par*2+2;
            dat[par]=merge(dat[c1],dat[c2]);
            pos=par;
        }
    }
    ll query(int a,int b){
        T res=query_impl(a,b,0,0,N);
        return accumulate(res.begin(),res.end(),0LL);
    }
    
};

vector<ll> asum;
ll dfs(int a,int b,int lb,int ub,SegmentTree& seg){
    if(a==b) return 0;
    int mid=(a+b)/2;
    int opt=max(lb,mid);
    ll res=0;
    for(int i=max(lb,mid);i<ub;i++){
        ll sc=seg.query(mid,i+1)-(asum[i]-asum[mid]);
        if(res<sc){
            opt=i;
            res=sc;
        }
    }

    ll lres=dfs(a,mid,lb,opt+1,seg);
    ll rres=dfs(mid+1,b,max(opt-1,0),ub,seg);
    return max({lres,rres,res});
}
int main(){
    int n,m;
    cin>>n>>m;
    
    vector<ll> a(n-1);
    asum.assign(n,0);
    for(int i=0;i<n-1;i++){
        cin>>a[i];
    }
    for(int i=0;i<n-1;i++){
        asum[i+1]=asum[i]+a[i];
    }
    
    vector<vector<ll>> b(n,vector<ll>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>b[i][j];
        }
    }
    SegmentTree seg(n,m);
    for(int i=0;i<n;i++) seg.update(i,b[i]);
    cout<<dfs(0,n,0,n,seg)<<endl;

    return 0;
}

Submission Info

Judge Result