knightL

B

Mar 26th, 2012
376
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <map>
  8. using namespace std;
  9.  
  10. #define REP(i,n) for(int i=0;i<(n);i++)
  11. #define FOR(i,a,b) for(int i=(a);i<(b);i++)
  12. #define FORD(i,a,b) for(int i=(a);i>(b);i--)
  13. typedef long long ll;
  14. typedef unsigned ui;
  15. typedef unsigned long long ull;
  16.  
  17. int nextint()
  18. {
  19.     int t;
  20.     if(scanf("%d",&t)!=1)
  21.     {
  22.         fprintf(stderr,"Failed to read int\n");
  23.         exit(0);
  24.     }
  25.     return t;
  26. }
  27. int n;
  28. int a[400][400];
  29. int sum[2*400][401];
  30. int id[400][400];
  31.  
  32. int main()
  33. {
  34.     n=nextint();
  35.     REP(i,n) REP(j,n) a[i][j]=nextint();
  36.     REP(i,2*n-1)
  37.     {
  38.          int top=1;
  39.          REP(j,n) REP(k,n)
  40.             if(j+k==i)
  41.             {              
  42.                 sum[i][top]=sum[i][top-1]+a[j][k];
  43.                 id[j][k]=top;
  44.                 top++;
  45.             }
  46.     }
  47.     int res=-1000000000;
  48.     REP(i,n) REP(j,n)
  49.     {
  50.         int s=0;
  51.         REP(k,n)
  52.         {
  53.             if(i+k==n||j+k==n) break;
  54.             s+=a[i+k][j+k];
  55.             res=max(res,s-(sum[i+j+k][id[i+k][j]]-sum[i+j+k][id[i][j+k]-1]));
  56.         }
  57.     }
  58.     printf("%d\n",res);
  59. }
Advertisement
Add Comment
Please, Sign In to add comment