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];
  28. vector<bool>vis;
  29.  
  30. ll rec(int c,int r,int cnt=0) {
  31.     if (cnt == n) {
  32.         ll black = 0, c_b = c;
  33.         for (int i = 1; i <= n; ++i) {
  34.             if (!vis[i])black += arr[i][c_b], c_b++;
  35.         }
  36.         return black;
  37.     }
  38.     ll &ret = dp[c][r];
  39.     if (~ret)return ret;
  40.     ret = max(ret, rec(c, r, cnt + 1));
  41.     for (int i = r + 1; i <= n; ++i) {
  42.         vis[i] = 1;
  43.         ret = max(ret, rec(c + 1, i, cnt + 1) + arr[i][c]);
  44.         vis[i] = 0;
  45.     }
  46.     return ret;
  47. }
  48. void solve() {
  49.     cin >> n;
  50.     vis=vector<bool>(n+2);
  51.     for (int i = 1; i <= n; ++i) {
  52.         for (int j = 1; j <= n; ++j) {
  53.             cin >> arr[i][j];
  54.         }
  55.     }
  56.     memo(dp,-1);
  57.     cout<<rec(1,0);
  58. }
  59. int main() {
  60.     IOS
  61.     File();
  62.     int tc = 1;
  63.     cin >> tc;
  64.     for (int i = 1; i <= tc; ++i) {
  65.         solve();
  66.         if (i < tc) cout << "\n";
  67.     }
  68.  
  69.     return 0;
  70. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sgj5jQ
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!