fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define nl "\n"
  4. #define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
  5. using namespace std;
  6. const ll mod = 1e9 + 7;
  7. ll fp(ll a,ll b) {
  8.     ll ans = 1, push = a;
  9.     while (b > 0) {
  10.         if (b & 1) { ans = (ans * push) % mod; }
  11.         push = (push * push) % mod;
  12.         b >>= 1;
  13.     }
  14.     return ans;
  15. }
  16. int main() {
  17.     baraa
  18.     ll t;
  19.     cin >> t;
  20.     while (t--) {
  21.         ll n;
  22.         cin >> n;
  23.         vector<vector<ll> > a(n, vector<ll>(n, 0));
  24.         for (ll i = 0; i < n; i++)
  25.             for (ll j = 0; j < n; j++)
  26.                 cin >> a[i][j];
  27.         ll mxi = -1e16;
  28.         for (ll black = 0; black <= n; black++) {
  29.             ll white = n - black;
  30.             vector<vector<ll> > dp(n + 2, vector<ll>(n + 2, -1e17));
  31.             function<ll(ll, ll, ll)> solve = [&](ll i, ll j, ll k)-> ll {
  32.                 if (i == n)return (j == black ? 0 : (ll) -1e16);
  33.                 if (dp[i][j] != (ll) -1e17)return dp[i][j];
  34.                 ll op1 = -1e16, op2 = -1e16;
  35.                 if (j != black)op1 = solve(i + 1, j + 1, k) + a[i][j];
  36.                 if (k != white)op2 = solve(i + 1, j, k + 1) + a[i][black + k];
  37.                 return dp[i][j] = max(op1, op2);
  38.             };
  39.             mxi = max(mxi, solve(0, 0, 0));
  40.         }
  41.         cout << mxi << nl;
  42.     }
  43.     return 0;
  44. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
 3
 2
 5 5
 10 4
 2
 1 4
 3 2
 3
 1 110 1
 100 5 9
 10 7 9
stdout
copy 
15
7
219
https://ideone.com/1ummGA
language:
C++14 (gcc 8.3)
created:
2 days 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!