#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin>>n; vector<int> prevleft(n,0),prevright(n,0); int m = -1000; for(int i=0;i<n;++i){ vector<int> input(n); for(int j=0;j<n;++j) cin>>input[j]; vector<int> left(n),right(n); left[0]=input[0]+max(0,prevright[0]); for(int j=1;j<n;++j) left[j]=input[j]+max(max(0,left[j-1]),prevright[j]); right[n-1]=input[n-1]+max(0,prevleft[n-1]); for(int j=n-2;j>=0;--j) right[j]=input[j]+max(max(0,right[j+1]),prevleft[j]); for(int j=0;j<n;++j){ prevleft[j]=max(prevleft[j]+input[j],left[j]); prevright[j]=max(prevright[j]+input[j],right[j]); m=max(max(m,prevleft[j]),prevright[j]); } //for(int j=0;j<n;++j) cout<<prevleft[j]<<' '; //cout<<" "; //for(int j=0;j<n;++j) cout<<prevright[j]<<' '; //cout<<'\n'; } cout<<m<<'\n'; }#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin>>n; vector<int> prevleft(n,0),prevright(n,0); int m = -1000; for(int i=0;i<n;++i){ vector<int> input(n); for(int j=0;j<n;++j) cin>>input[j]; vector<int> left(n),right(n); left[0]=input[0]+max(0,prevright[0]); for(int j=1;j<n;++j) left[j]=input[j]+max(max(0,left[j-1]),prevright[j]); right[n-1]=input[n-1]+max(0,prevleft[n-1]); for(int j=n-2;j>=0;--j) right[j]=input[j]+max(max(0,right[j+1]),prevleft[j]); for(int j=0;j<n;++j){ prevleft[j]=max(prevleft[j]+input[j],left[j]); prevright[j]=max(prevright[j]+input[j],right[j]); m=max(max(m,prevleft[j]),prevright[j]); } //for(int j=0;j<n;++j) cout<<prevleft[j]<<' '; //cout<<" "; //for(int j=0;j<n;++j) cout<<prevright[j]<<' '; //cout<<'\n'; } cout<<m<<'\n'; }