fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  7. #define all(v) v.begin(),v.end()
  8. #define sz(s) (int)(s).size()
  9. #define ll long long
  10. #define ld long double
  11. #define el "\n"
  12. #define PI  3.141592653589793
  13. #define fx(x) fixed<<setprecision(x)
  14. #define F first
  15. #define S second
  16. #define memo(mem, val) memset(mem, val, sizeof(mem))
  17. #define IOS ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  18.  
  19. void File() {
  20. #ifndef ONLINE_JUDGE
  21.     freopen("input.txt", "r", stdin);
  22.     freopen("output.txt", "w", stdout);
  23. #endif
  24. }
  25. const int N=1e5+5;
  26. int n;
  27. ll arr[302][302],dp[302][302][302],vis[302][302][302];
  28. int val,id=1;
  29. ll rec(int c_w,int r,int c_b) {
  30.     if (c_w == val) {
  31.         int x=c_b;
  32.         ll sum=0;
  33.         for (int i = r+1; i <=n ; ++i) {
  34.             sum+=arr[i][x];
  35.             x++;
  36.         }
  37.         return sum;
  38.     }
  39.     ll &ret = dp[c_w][r][c_b];
  40.     if (vis[c_w][r][c_b]==id)return ret;
  41.     vis[c_w][r][c_b]=id;
  42.     for (int i = r + 1; i <= n; ++i) {
  43.         ll x = 0, tmp = c_b;
  44.         for (int j = r + 1; j < i; ++j) {
  45.             x += arr[j][tmp];
  46.             tmp++;
  47.         }
  48.         ret = max(ret, rec(c_w + 1, i, tmp) + x + arr[i][c_w]);
  49.     }
  50.     return ret;
  51. }
  52. void solve() {
  53.     cin >> n;
  54.     for (int i = 1; i <= n; ++i) {
  55.         for (int j = 1; j <= n; ++j) {
  56.             cin >> arr[i][j];
  57.         }
  58.     }
  59.     memo(dp,-1);
  60.     memo(vis,0);
  61.     ll ans=0;
  62.     for (int i = 1; i <=n ; ++i) {
  63.         id++;
  64.         val=i;
  65.         ans= max(ans, rec(min(i,1),0,i+1));
  66.     }
  67.  
  68.     cout<<ans;
  69. }
  70. int main() {
  71.     IOS
  72.     File();
  73.     int tc = 1;
  74.     cin >> tc;
  75.     for (int i = 1; i <= tc; ++i) {
  76.         solve();
  77.         if (i < tc) cout << "\n";
  78.     }
  79.  
  80.     return 0;
  81. }
Success #stdin #stdout 0.07s 434572KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Yzn4hI
language:
C++14 (gcc 8.3)
created:
17 hours 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!