#include #define VM -1000000 using namespace std; ifstream f("main.in"); ofstream g("main.out"); int v[1005][1005]; int maxis[1005][1005]; int maxid[1005][1005]; int maxi[1005][1005]; int maxim(int a,int b,int c) { if(a>n; int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) cin>>v[i][j]; for(i=1;i<=n;i++) maxi[1][i]=maxis[1][i]=maxid[i][j]=max(v[1][i],v[1][i]+maxi[1][i-1]); for(i=2;i<=n;i++) { int maxi1=VM,maxi2=VM; for(j=1;j<=n;j++) { maxis[i][j]=maxim(v[i][j],v[i][j]+maxi[i-1][j],v[i][j]+maxis[i][j-1]); if(maxis[i][j]>maxi1) maxi1=maxis[i][j]; } for(j=n;j>=1;j--) { maxid[i][j]=maxim(v[i][j],v[i][j]+maxi[i-1][j],v[i][j]+maxid[i][j+1]); if(maxid[i][j]>maxi2) maxi2=maxid[i][j]; } if(maxi1>maxi2) for(j=1;j<=n;j++) maxi[i][j]=maxis[i][j]; else for(j=1;j<=n;j++) maxi[i][j]=maxid[i][j]; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(rez