fork download 
  1. #include <vector>
  2. #include <iostream>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. using ll = long long;
  9. using ull = unsigned long long;
  10.  
  11. using vi = vector<int>;
  12. using vll = vector<ll>;
  13. using vvi = vector<vi>;
  14. using vvll = vector<vll>;
  15. using pii = vector<pair<int, int>>;
  16. using pll = vector<pair<ll, ll>>;
  17. using vvpii = vector<vector<pii>>;
  18.  
  19. template <typename T>
  20. using max_pq = priority_queue<T>;
  21. template <typename T>
  22. using min_pq = priority_queue<T, vector<T>, greater<T>>;
  23.  
  24. constexpr int MOD = 1000000007;
  25. constexpr int IINF = 1000000000;
  26. constexpr ll LLINF = 1000000000000000000;
  27. constexpr double EPS = 1e-9;
  28.  
  29. void set_io(string name = "") {
  30.     if (!name.empty()) {
  31.         freopen((name + ".INP").c_str(), "r", stdin);
  32.         freopen((name + ".OUT").c_str(), "w", stdout);
  33.     }
  34.  
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(nullptr);
  37. }
  38.  
  39. template <typename T>
  40. void read_vector(vector<T>& vec, const size_t n) {
  41.     vec.resize(n);
  42.     for (size_t i = 0; i < n; ++i) {
  43.         cin >> vec[i];
  44.     }
  45. }
  46.  
  47. template <typename T>
  48. void print_vector(const vector<T>& vec) {
  49.     cout << "[";
  50.     for (size_t i = 0; i < vec.size(); ++i) {
  51.         cout << vec[i];
  52.         if (i < vec.size() - 1) {
  53.             cout << ", ";
  54.         }
  55.     }
  56.     cout << "]" << endl;
  57. }
  58.  
  59. template <typename T>
  60. void print_2d_vector(const vector<vector<T>>& vec) {
  61.     cout << "[";
  62.     for (size_t i = 0; i < vec.size(); ++i) {
  63.         if (i > 0) cout << " "; 
  64.  
  65.         cout << "[";
  66.         for (size_t j = 0; j < vec[i].size(); ++j) {
  67.             cout << vec[i][j];
  68.             if (j < vec[i].size() - 1) {
  69.                 cout << ", ";
  70.             }
  71.         }
  72.         cout << "]";
  73.         if (i < vec.size() - 1) {
  74.             cout << "," << endl;
  75.         }
  76.     }
  77.     cout << "]" << endl;
  78. }
  79.  
  80. void log() {cerr << endl;}
  81. template <typename T, typename... Args>
  82. void log(T first, Args... args) {
  83.     cerr << first << ' ';
  84.     log(args...);
  85. }
  86.  
  87. template <bool IsDirected, bool IsWeighted>
  88. auto read_graph(int n, int m) {
  89.     if constexpr (IsWeighted) {
  90.         vvpii adj(n);
  91.         for (int i = 0; i < m; ++i) {
  92.             int u, v, w;
  93.             cin >> u >> v >> w;
  94.             --u; --v;
  95.             adj[u].emplace_back(v, w);
  96.             if constexpr (!IsDirected) adj[v].emplace_back(u, w);
  97.         }
  98.         return adj;
  99.     } else {
  100.         vvi adj(n);
  101.         for (int i = 0; i < m; ++i) {
  102.             int u, v;
  103.             cin >> u >> v;
  104.             --u; --v;
  105.             adj[u].push_back(v);
  106.             if constexpr (!IsDirected) adj[v].push_back(u);
  107.         }
  108.         return adj;
  109.     }
  110. }
  111.  
  112. template<typename T>
  113. bool chmin(T& a, const T& b) {
  114.     if (b < a) { a = b; return true; }
  115.     return false;
  116. }
  117.  
  118. template<typename T>
  119. bool chmax(T& a, const T& b) {
  120.     if (a < b) { a = b; return true; }
  121.     return false;
  122. }
  123.  
  124. template <typename T>
  125. vector<long long> make_prefix_sum(const vector<T>& arr) {
  126.     int n = arr.size();
  127.     vector<ll> pref(n + 1, 0);
  128.     for (int i = 0; i < n; ++i) {
  129.         pref[i + 1] = pref[i] + arr[i];
  130.     }
  131.     return pref;
  132. }
  133.  
  134. template <typename T>
  135. bool is_valid(int r, int c, int R, int C) {
  136.     return r >= 0 && r < R && c >= 0 && c < C;
  137. }
  138.  
  139. void sub1(vvi& grid) {
  140.     int n = (grid.size() + 1) / 2;
  141.     vector<int> max_row;
  142.     for (auto& row : grid) {
  143.         max_row.push_back(*max_element(row.begin(), row.end()));
  144.     }
  145.     vector<vvll> dp(2, vvll(2 * n));
  146.     for (int i = 0; i <= n; ++i) {
  147.         dp[0][i].resize(n + i - 1, 0);
  148.         dp[1][i].resize(n + i - 1, 0);
  149.  
  150.     }
  151.     for (int i = n + 1; i < 2 * n; ++i) {
  152.         dp[0][i].resize(2 * n - 1 - (i - n), 0);
  153.         dp[1][i].resize(2 * n - 1 - (i - n), 0);
  154.     }
  155.  
  156.     for (int t = 0; t < 2; ++t) {
  157.         for (int i = 1; i < 2 * n; ++i) {
  158.             int curr_sz = dp[0][i].size();
  159.             int prev_sz = dp[0][i - 1].size();
  160.             for (int j = 0; j < curr_sz; ++j) {
  161.                 int a, b;
  162.                 ll s = 0;
  163.                 if (i <= n) {a = j - 1; b = j;}
  164.                 else {a = j; b = j + 1;}
  165.                 if (a >= 0) {
  166.                     s = dp[t][i - 1][a];
  167.                 }
  168.                 if (b < prev_sz) {
  169.                     s = max(s, dp[t][i - 1][b]);
  170.                 }
  171.                 dp[t][i][j] = max(dp[t][i][j], s + grid[i - 1][j]);
  172.                 if (t == 0) {
  173.                     dp[1][i][j] = max(dp[1][i][j], s + max_row[i - 1]);
  174.                 }
  175.             }
  176.         }
  177.     }
  178.  
  179.     cout << max(*max_element(dp[0][2 * n - 1].begin(), dp[0][2 * n - 1].end()),
  180.                 *max_element(dp[1][2 * n - 1].begin(), dp[1][2 * n - 1].end())) << '\n';
  181. }
  182.  
  183. void sub2(vvi& grid) {
  184.     int n = (grid.size() + 1) / 2;
  185.     vector<pair<int, int>> stats(2 * n - 1);
  186.     for (int i = 0; i < 2 * n - 1; ++i) {
  187.         int m1 = -1, m2 = -1;
  188.         for (int val : grid[i]) {
  189.             if (val > m1) {m2 = m1; m1 = val;}
  190.             else if (val > m2) {m2 = val;}
  191.         }
  192.         stats[i] = {m1, m2};
  193.     }
  194.     vector<vector<vvll>> dp(2, vector<vvll>(2 * n));
  195.     for (int i = 0; i <= n; ++i) {
  196.         dp[0][i].resize(n + i - 1, vll(n + i - 1, 0));
  197.         dp[1][i].resize(n + i - 1, vll(n + i - 1, 0));
  198.  
  199.     }
  200.     for (int i = n + 1; i < 2 * n; ++i) {
  201.         dp[0][i].resize(2 * n - 1 - (i - n), vll(2 * n - 1 - (i - n), 0));
  202.         dp[1][i].resize(2 * n - 1 - (i - n), vll(2 * n - 1 - (i - n), 0));
  203.     }
  204.  
  205.     for (int t = 0; t < 2; ++t) {
  206.         for (int i = 1; i < 2 * n; ++i) {
  207.             int curr_sz = dp[0][i].size();
  208.             int prev_sz = dp[0][i - 1].size();
  209.             for (int j = 0; j < curr_sz; ++j) {
  210.                 for (int k = j + 1; k < curr_sz; ++k) {
  211.                     int a, b, c, d;
  212.                     ll s = 0;
  213.                     if (i <= n) {a = j - 1; b = j; c = k - 1; d = k;}
  214.                     else {a = j; b = j + 1; c = k; d = k + 1;}
  215.                     if (a >= 0) {
  216.                         if (c > a) {
  217.                             s = max(s, dp[t][i - 1][a][c]);
  218.                         }
  219.                         if (a < d && d < prev_sz) {
  220.                             s = max(s, dp[t][i - 1][a][d]);
  221.                         }
  222.                     }
  223.                     if (b < prev_sz) {
  224.                         if (c > b) {
  225.                             s = max(s, dp[t][i - 1][b][c]);
  226.                         }
  227.                         if (b < d && d < prev_sz) {
  228.                             s = max(s, dp[t][i - 1][b][d]);
  229.                         }
  230.                     }
  231.                     dp[t][i][j][k] = max(dp[t][i][j][k], s + grid[i - 1][j] + grid[i - 1][k]);
  232.                     if (t == 0) {
  233.                         if (stats[i - 1].first != grid[i - 1][k])
  234.                             dp[1][i][j][k] = max(dp[1][i][j][k], s + stats[i - 1].first + grid[i - 1][k]);
  235.                         else
  236.                             dp[1][i][j][k] = max(dp[1][i][j][k], s + stats[i - 1].second + grid[i - 1][k]);
  237.                         if (stats[i - 1].first != grid[i - 1][j])
  238.                             dp[1][i][j][k] = max(dp[1][i][j][k], s + stats[i - 1].first + grid[i - 1][j]);
  239.                         else
  240.                             dp[1][i][j][k] = max(dp[1][i][j][k], s + stats[i - 1].second + grid[i - 1][j]);
  241.                     }
  242.                 }
  243.             }
  244.         }
  245.     }
  246.     ll ans = 0;
  247.     for (int i = 0; i < n; ++i) {
  248.         for (int j = i + 1; j < n; ++j) {
  249.             ans = max({ans, dp[0][2 * n - 1][i][j], dp[1][2 * n - 1][i][j]});
  250.         }
  251.     }
  252.     cout << ans << '\n';
  253. }
  254.  
  255. int main() {
  256.     set_io();
  257. 	int n, k;
  258.     cin >> n >> k;
  259.     vvi grid(2 * n - 1);
  260.     for (int i = 0; i < n; ++i) {
  261.         read_vector(grid[i], n + i);
  262.     }
  263.     for (int i = n; i < 2 * n - 1; ++i) {
  264.         read_vector(grid[i], 2 * n - 2 - (i - n));
  265.     }
  266.  
  267.     if (k == 1) {
  268.         sub1(grid);
  269.     } else {
  270.         sub2(grid);
  271.     }
  272. }
  273.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin 
3 2
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4
stdout 
36
https://ideone.com/zsGlBJ
language:
C++ (gcc 8.3)
created:
1 day 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!