记录编号	593281	评测结果	AAAAAAAAAA
题目名称	Partition	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	10.722 s
提交时间	2024-08-28 21:44:30	内存使用	79.22 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 2010
#define ll long long
ll f1[MAXN][MAXN],f2[MAXN][MAXN],a[MAXN][MAXN],d[MAXN][MAXN];
ll n,m,maxz=LONG_LONG_MIN,ans=LONG_LONG_MIN,ansz=LONG_LONG_MIN,sum;
int main(){
    freopen("partition.in","r",stdin);
    freopen("partition.out","w",stdout);
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>a[i][j];
            sum+=a[i][j];
            d[i][j]=d[i-1][j]+a[i][j];
        }
    }
//    for(ll i=1;i<=n;i++){
//        for(ll j=1;j<=m;j++)cout<<d[i][j]<<" ";
//        cout<<endl;
//    }
    for(ll i=1;i<=m;i++){
        maxz=LONG_LONG_MIN;
        for(ll j=1;j<=n+1;j++){
            if(f1[i-1][j]>maxz)maxz=f1[i-1][j];
            f1[i][j]=maxz+d[n][i]-d[j-1][i];
        }  
    }
    for(ll i=1;i<=n+1;i++)ans=max(ans,f1[m][i]*2);
//    cout<<ans<<endl;
    for(ll i=m;i;i--){
        maxz=LONG_LONG_MIN;
        for(ll j=1;j<=n+1;j++){
            if(f2[i+1][j]>maxz)maxz=f2[i+1][j];
            f2[i][j]=maxz+d[n][i]-d[j-1][i];
        }  
    }
    for(ll i=1;i<=n+1;i++){
        ansz=max(ansz,ans+f2[1][i]+sum);
    }
    cout<<ansz;
    return 0;
}