fork download
copy 
  1. //#pragma GCC optimize("O3", "unroll-loops")
  2. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. //#define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define gcd __gcd
  28. #define pushb push_back
  29. #define popb pop_back
  30. #define pushf push_front
  31. #define popf pop_front
  32. #define mul2x(a, x) a << x
  33. #define div2x(a, x) a >> x
  34. #define lcm(a, b) (a / __gcd(a, b) * b)
  35. #define log_base(x, base) log(x) / log(base)
  36. #define debug cerr << "No errors!"; exit(0);
  37. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  38. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  39. #define fors(i, a, b) for (int i = a; i >= b; --i)
  40. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  41. #define pqueue priority_queue
  42. #define sqrt sqrtl
  43. #define i128 __int128
  44. #define popcount __builtin_popcountll
  45. #define BIT(x, i) (((x) >> (i)) & 1)
  46. #define MASK(x) ((1LL) << (x))
  47. #define want_digit(x) cout << fixed << setprecision(x);
  48. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  49. #define mapa make_pair
  50. using namespace std;
  51. const int MOD = 1e9 + 7; // 998244353
  52. const int inf = 1e9;
  53. const ll INF = 1e18;
  54. const int N = 100;
  55.  
  56. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  57. ll random(const ll &L, const ll &R) {
  58.     return uniform_int_distribution<ll> (L, R) (rng);
  59. }
  60.  
  61. template <class X, class Y>
  62. bool maximize(X &x, const Y &y) {
  63.     return x < y ? x = y, true : false;
  64. }
  65.  
  66. int n, k, a[N * 2 + 5][N * 2 + 5];
  67.  
  68. ll dp[N * 2 + 5][N * 2 + 5][2];
  69. ll mx[N * 2 + 5];
  70. void sub1() {
  71.     forw (i, 1, n) {
  72.         dp[1][i][0] = a[1][i];
  73.         dp[1][i][1] = mx[1];
  74.     }
  75.  
  76.     forw (i, 1, n - 1) {
  77.         forw (j, 1, n + i - 1) {
  78.             forw (p, 0, 1) {
  79.                 maximize(dp[i + 1][j][p], dp[i][j][p] + a[i + 1][j]);
  80.                 maximize(dp[i + 1][j + 1][p], dp[i][j][p] + a[i + 1][j + 1]);
  81.                 if (p) {
  82.                     ll tmp = dp[i][j][0] + mx[i + 1];
  83.                     maximize(dp[i + 1][j][1], tmp);
  84.                     maximize(dp[i + 1][j + 1][1], tmp);
  85.                 }
  86.             }
  87.         }
  88.     }
  89.  
  90.     forw (i, n, n * 2 - 2) {
  91.         forw (j, 1, 3 * n - i - 1) {
  92.             forw (p, 0, 1) {
  93.                 maximize(dp[i + 1][j][p], dp[i][j][p] + a[i + 1][j]);
  94.                 maximize(dp[i + 1][j - 1][p], dp[i][j][p] + a[i + 1][j - 1]);
  95.                 if (p) {
  96.                     ll tmp = dp[i][j][0] + mx[i + 1];
  97.                     maximize(dp[i + 1][j][1], tmp);
  98.                     maximize(dp[i + 1][j - 1][1], tmp);
  99.                 }
  100.             }
  101.         }
  102.     }
  103.  
  104.     ll ans = 0;
  105.     forw (i, 1, n) maximize(ans, max(dp[n * 2 - 1][i][0], dp[n * 2 - 1][i][1]));
  106.     cout << ans << endl;
  107. }
  108.  
  109. ll f[N * 2 + 5][N * 2 + 5][2][N * 2 + 5][2];
  110. void sub2() {
  111.     forw (i, 1, n) {
  112.         forw (j, i + 1, n) {
  113.             f[1][i][0][j][0] = a[1][i] + a[1][j];
  114.             f[1][i][1][j][0] = mx[1] + a[1][j];
  115.             f[1][i][0][j][1] = a[1][i] + mx[1];
  116.             f[1][i][1][j][1] = mx[1] + mx[1];
  117.         }
  118.     }
  119.  
  120.     forw (i, 1, n - 1) {
  121.         int lim = n + i - 1;
  122.         forw (j, 1, lim) {
  123.             forw (used1, 0, 1) {
  124.                 forw (p, j + 1, lim) {
  125.                     forw (used2, 0, 1) {
  126.                         ll curr = f[i][j][used1][p][used2];
  127.                         forw (add1, 0, 1) forw (add2, 0, 1) {
  128.                             int _j = j + add1, _p = p + add2;
  129.                             if (_j >= _p) continue;
  130.                             maximize(f[i + 1][_j][used1][_p][used2], curr + a[i + 1][_j] + a[i + 1][_p]);
  131.                             if (!used1)
  132.                                 maximize(f[i + 1][_j][1][_p][used2], curr + mx[i + 1] + a[i + 1][_p]);
  133.                             if (!used2)
  134.                                 maximize(f[i + 1][_j][used1][_p][1], curr + a[i + 1][_j] + mx[i + 1]);
  135.                             if (!(used1 | used2))
  136.                                 maximize(f[i + 1][_j][1][_p][1], curr + (mx[i + 1] << 1));
  137.                         }
  138.                     }
  139.                 }
  140.             }
  141.         }
  142.     }
  143.  
  144.     forw (i, n, n * 2 - 2) {
  145.         int lim = 3 * n - i - 1;
  146.         forw (j, 1, lim) {
  147.             forw (used1, 0, 1) {
  148.                 forw (p, j + 1, lim) {
  149.                     forw (used2, 0, 1) {
  150.                         ll curr = f[i][j][used1][p][used2];
  151.                         forw (add1, -1, 0) forw (add2, -1, 0) {
  152.                             int _j = j + add1, _p = p + add2;
  153.                             if (_j >= _p) continue;
  154.                             maximize(f[i + 1][_j][used1][_p][used2], curr + a[i + 1][_j] + a[i + 1][_p]);
  155.                             if (!used1)
  156.                                 maximize(f[i + 1][_j][1][_p][used2], curr + mx[i + 1] + a[i + 1][_p]);
  157.                             if (!used2)
  158.                                 maximize(f[i + 1][_j][used1][_p][1], curr + a[i + 1][_j] + mx[i + 1]);
  159.                             if (!(used1 | used2))
  160.                                 maximize(f[i + 1][_j][1][_p][1], curr + (mx[i + 1] << 1));
  161.                         }
  162.                     }
  163.                 }
  164.             }
  165.         }
  166.     }
  167.  
  168.     ll ans = 0;
  169.     forw (i, 1, n) forw (j, i + 1, n) {
  170.         forw (used1, 0, 1) forw (used2, 0, 1) {
  171.             maximize(ans, f[n * 2 - 1][i][used1][j][used2]);
  172.         }
  173.     }
  174.     cout << ans << endl;
  175. }
  176.  
  177. void solve() {
  178.     cin >> n >> k;
  179.     forw (i, 1, n * 2 - 1) {
  180.         forw (j, 1, (i <= n ? n + i - 1 : 3 * n - 1 - i))
  181.             cin >> a[i][j], maximize(mx[i], a[i][j]);
  182.     }
  183.     if (k == 1) sub1();
  184.     else sub2();
  185. }
  186.  
  187. signed main() {
  188.     ios::sync_with_stdio(false), cin.tie(nullptr);
  189.     srand(time(NULL));
  190.     #define name "test"
  191.     /*
  192.     if (fopen(name".INP", "r")) {
  193.         freopen(name".INP", "r", stdin);
  194.         freopen(name".OUT", "w", stdout);
  195.     }
  196.     */
  197.     bool testCase = false;
  198.     int numTest = 1;
  199. //    cin >> numTest;
  200.     forw (i, 1, numTest) {
  201.         if (testCase) cout << "Case " << i << ": ";
  202.         solve();
  203.     }
  204.     return 0;
  205. }
  206.  
Success #stdin #stdout 0.01s 5608KB
comments (?)
stdin
copy 
3 2
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4
stdout
copy 
42
https://ideone.com/HS3MLg
language:
C++14 (gcc 8.3)
created:
5 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!