Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <cstdlib>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- #include <map>
- using namespace std;
- #define REP(i,n) for(int i=0;i<(n);i++)
- #define FOR(i,a,b) for(int i=(a);i<(b);i++)
- #define FORD(i,a,b) for(int i=(a);i>(b);i--)
- typedef long long ll;
- typedef unsigned ui;
- typedef unsigned long long ull;
- int nextint()
- {
- int t;
- if(scanf("%d",&t)!=1)
- {
- fprintf(stderr,"Failed to read int\n");
- exit(0);
- }
- return t;
- }
- int n;
- int a[400][400];
- int sum[2*400][401];
- int id[400][400];
- int main()
- {
- n=nextint();
- REP(i,n) REP(j,n) a[i][j]=nextint();
- REP(i,2*n-1)
- {
- int top=1;
- REP(j,n) REP(k,n)
- if(j+k==i)
- {
- sum[i][top]=sum[i][top-1]+a[j][k];
- id[j][k]=top;
- top++;
- }
- }
- int res=-1000000000;
- REP(i,n) REP(j,n)
- {
- int s=0;
- REP(k,n)
- {
- if(i+k==n||j+k==n) break;
- s+=a[i+k][j+k];
- res=max(res,s-(sum[i+j+k][id[i+k][j]]-sum[i+j+k][id[i][j+k]-1]));
- }
- }
- printf("%d\n",res);
- }
Advertisement
Add Comment
Please, Sign In to add comment