fork download 
  1. #include <bits/stdc++.h>
  2. #define int long long 
  3. using namespace std;
  4.  
  5. const int N  = 5e3+2, inf = 5e17 ;
  6. int a[N][N] , dp1[N][N] , dp2[N][N];
  7. void solve()
  8.   {
  9.      int n , m , i , j ,k ,l ;
  10.       cin >> n ;
  11.  
  12.       for(int i = 0 ; i <= n + 1 ; i++) for(int j = 0 ; j <= n + 1 ;j++)a[i][j] = dp1[i][j] = dp2[i][j] = -inf;
  13.       int ans = -inf ;
  14.       for(int i = 1 ; i <= n ; i++)
  15.          for(int j = 1 ; j <= n ; j++)
  16.             {
  17.                cin >> a[i][j] ;
  18.                int curr =  max(dp1[i-1][j] , dp1[i][j-1]);
  19.                dp1[i][j] = max(a[i][j] + i + j ,curr);
  20.                ans = max( ans , curr + a[i][j] - i - j);
  21.             }
  22.     for(int i = 1 ; i <= n ; i++)
  23.       for(int j = n ; j >= 1 ; j-- )
  24.           {
  25.               int curr = max(dp2[i-1][j] , dp2[i][j+1]);
  26.               dp2[i][j] = max(a[i][j] + i - j , curr);
  27.               ans = max( ans , curr + a[i][j] - i + j);
  28.           }
  29.     cout << ans <<"\n";
  30.   }
  31. signed main()
  32.  {
  33.  
  34.   int testCases ;
  35.   cin >> testCases ;
  36.  
  37.   while(testCases--)solve();
  38.  
  39.  
  40.  return 0 ;
  41.  }
Success #stdin #stdout 0.01s 7768KB
comments (?)
stdin 
1
4
1 9 1 1
1 1 4 1
3 4 1 2
1 2 7 7
stdout 
13
https://ideone.com/WxYE8d
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!