hitarth_gg

amazonOA Reddit

Mar 12th, 2025
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.49 KB | None | 0 0
  1. // clang-format off
  2. #include <bits/stdc++.h>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5.  
  6. using namespace std;
  7. using namespace chrono;
  8. using namespace __gnu_pbds;
  9.  
  10. /* ----------------------- int128 ----------------------- */
  11. // typedef __int128 lll;
  12. // istream &operator>>(istream &cin, lll &x) { x=0; static string s; cin>>s; for (char c:s) x=x*10+(c-'0'); return cin; }
  13. // ostream &operator<<(ostream &cout, lll x) { static char s[60]; int tp=1; s[0]='0'+(x%10); while (x/=10) s[tp++]='0'+(x%10); while (tp--) cout<<s[tp]; return cout; }
  14. /* ------------------------------------------------------ */
  15. /* ------------------------ INPUT ----------------------- */
  16. // 1
  17. #define G(x) ll x; cin >> x;
  18. #define reS(x) string x; cin >> x;
  19. // 2
  20. #define re(...) ll __VA_ARGS__; read(__VA_ARGS__)
  21. void read() {}
  22. template <typename T, typename... Args>
  23. void read(T& first, Args&... args) {
  24.     cin >> first;
  25.     read(args...);
  26. }
  27. // 3
  28. #define reV(v, n) vll v(n); cinv(v);
  29. /* ------------------------------------------------------ */
  30. /* ----------------------- OUTPUT ----------------------- */
  31. // Base case: single variable
  32. template <typename T>
  33. void print(const T& t) {
  34.     std::cout << t;
  35. }
  36.  
  37. // Recursive case: multiple variables
  38. template <typename T, typename... Args>
  39. void print(const T& first, const Args&... rest) {
  40.     std::cout << first << " ";
  41.     print(rest...);
  42. }
  43. /* ------------------------------------------------------ */
  44. /* ------------------------ debug ----------------------- */
  45. // #ifndef ONLINE_JUDGE
  46. #ifdef hitarth
  47. #include "D:\Compi\Headers\debug3.h"
  48. #else
  49. #define debug(...)
  50. #define debugArr(...)
  51. #endif
  52. /* ------------------------------------------------------ */
  53.  
  54. #define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  55.  
  56. #define MOD 1000000007
  57. #define INF 1e18+9
  58. #define nl '\n'
  59. #define precision(x) cout<<fixed<<setprecision(x)
  60.  
  61. #define fr(i, x, n) for (ll i = x; i < n; i ++)
  62. #define loop(n) for(ll i=0;i<n;i++)
  63.  
  64. #define ll long long int
  65. #define ull unsigned long long int
  66. #define pb push_back
  67. #define mp make_pair
  68. #define fi first
  69. #define se second
  70.  
  71. #define vll vector<ll>
  72. #define vp vector<pair<ll,ll>>
  73.  
  74. template <typename T>
  75. struct matrix : vector<vector<T>> {matrix(size_t n, size_t m, T value):vector<vector<T>>(n, vector<T>(m, value)){}};
  76.  
  77. #define printVec(v) for(auto it:v)cout<<it<<' '; cout<<endl;
  78. #define cinv(v) for(auto &it:v) cin>>it;
  79.  
  80. #define vsort(v) sort(v.begin(), v.end())
  81. #define vsortrev(v) sort(v.rbegin(),v.rend())
  82. #define vrev(v) reverse(v.rbegin(),v.rend())
  83. #define v_sum(v) accumulate(v.begin(),v.end(),0LL)
  84. #define v_min(v) *min_element (v.begin(),v.end())
  85. #define v_max(v) *max_element (v.begin(),v.end())
  86. #define v_count(v, target) count(v.begin(), v.end(), target)
  87. #define UB(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x));
  88. #define LB(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x));
  89. #define UNIQUE(v) vsort(v), v.erase(unique(v.begin(), v.end()), v.end());
  90.  
  91. #define bitcount __builtin_popcountll
  92. #define bitCheck(n,k) ((n>>k)&1LL)
  93. #define bitSet(n,k) (n|(1LL<<k))
  94. #define bitClear(n,k) (n&(~(1LL<<k)))
  95. #define bitFlip(n,k) (n^(1LL<<k))
  96.  
  97. typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
  98. // priority_queue<long long, vector<long long>, greater<long long>> pq;
  99. /* ------------------------------------------------------ */
  100. ll mod_add(ll a, ll b, ll m=MOD);
  101. ll mod_mul(ll a, ll b, ll m=MOD);
  102. ll mod_sub(ll a, ll b, ll m=MOD);
  103. ll mod_div(ll a, ll b, ll m=MOD); // only for prime m
  104. ll binpow(ll a, ll b);
  105. ll binpow(ll a, ll b, ll m);
  106. ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
  107. ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
  108. ll mod_inverse(ll a, ll b);
  109. ll kadane( vector<ll> arr,ll n);
  110. ll ncr(ll n, ll r);
  111. ll ncr2(ll n, ll r);
  112. unsigned long long nCrModPFermat(unsigned long long n, int r, int mod = MOD);
  113. ll factorial(ll n);
  114. ll lcm(ll a, ll b);
  115.  
  116. bool is_prime(ll n);
  117. vector<bool> sieve(ll n); // vector<bool> isPrime = sieve(1000002);
  118.  
  119. ll extEuclid(ll a, ll b, ll& x, ll& y); // ll x, y; ll gcd = extEuclid(a, b, x, y); // ax + by = gcd(a, b)
  120. vector<long long> trial_division1(long long n);
  121. vll get_factors(ll num, ll upper_limit = 1000000, bool reset = false);
  122.  
  123. ll last_index(ll l, ll r, vll &v, bool (&comp)(ll, ll), ll target); // comp function should return true if v[mid] <= target
  124. ll first_index(ll l, ll r, vll &v, bool (&comp)(ll, ll), ll target); // comp function should return true if v[mid] < target
  125.  
  126.  
  127. /* ---------------------- snippets ---------------------- */
  128. // STRING: string_hashing | string_double_hashing/no_mod | rabin_karp | kmp | z_function
  129. // ARRAY: apply_permutation
  130. // OTHERS: custom_hash
  131. /* ------------------------------------------------------ */
  132. // clang-format on
  133.  
  134. vll f_dp(vector<ll> &w, ll k)
  135. {
  136.     ll n = w.size();
  137.  
  138.     matrix<ll> dp_max(k + 1, n + 1, -INF);
  139.     matrix<ll> dp_min(k + 1, n + 1, INF);
  140.  
  141.     for (ll i = 1; i <= k; i++)
  142.     {
  143.         for (ll j = i - 1; j < n; j++)
  144.         {
  145.             if (i == 1)
  146.             {
  147.                 dp_max[i][j] = w[0] + w[j];
  148.                 dp_min[i][j] = w[0] + w[j];
  149.             }
  150.             else
  151.             {
  152.                 for (ll z = i - 1; z <= j; z++)
  153.                 {
  154.                     dp_max[i][j] = max(dp_max[i][j], dp_max[i - 1][z - 1] + w[z] + w[j]);
  155.                     dp_min[i][j] = min(dp_min[i][j], dp_min[i - 1][z - 1] + w[z] + w[j]);
  156.                 }
  157.             }
  158.         }
  159.     }
  160.     vll ans;
  161.     ans.push_back(dp_min[k][n - 1]);
  162.     ans.push_back(dp_max[k][n - 1]);
  163.     return ans;
  164. }
  165.  
  166. void solve()
  167. {
  168.     re(n);
  169.     reV(v, n);
  170.     re(k);
  171.     vll ans = f_dp(v, k);
  172.     printVec(ans);
  173. }
  174.  
  175. // clang-format off
  176. int32_t main()
  177. {
  178.     fastio();
  179.  
  180.     clock_t begin = clock();
  181.     int t=1;
  182.     // cin >> t;
  183.     while(t--)
  184.     {
  185.         solve();
  186.     }
  187.     clock_t end = clock();
  188.     double duration = (double)(end - begin) / CLOCKS_PER_SEC;
  189. #ifndef ONLINE_JUDGE
  190.     // cerr << "Time: " << duration << endl;
  191. #endif
  192.  
  193.  
  194.     return 0;
  195. }
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218. /* ------------------------------------------------------ */
  219. /* ------------------------------------------------------ */
  220. /* ------------------------------------------------------ */
  221. ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
  222. ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
  223. ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
  224. ll mod_inverse(ll a, ll b) { return binpow(a, b - 2, b); }
  225. ll mod_div(ll a, ll b, ll m) {a = a % m;b = b % m; return (mod_mul(a, mod_inverse(b, m), m) + m) % m;} // only for prime m
  226.  
  227. ll binpow(ll a, ll b) {
  228.     ll res = 1;
  229.     while(b>0)
  230.     {
  231.         if(b&1)
  232.             res = res*a;
  233.         a=a*a;
  234.         b>>=1;
  235.     }
  236.     return res;
  237. }
  238. ll binpow(ll a, ll b, ll m) {
  239.     a %= m;
  240.     ll res = 1;
  241.     while (b > 0) {
  242.         if (b & 1)
  243.             res = res * a % m; // m = mod
  244.         a = a * a % m;
  245.         b >>= 1;
  246.     }
  247.     return res;
  248. }
  249. ll kadane( vector<ll> arr,ll n) {
  250.     ll max_end = 0;
  251.     ll mx =0;
  252.     for(ll i =0;i<n;i++){
  253.         max_end+=arr[i];
  254.         if(mx<max_end)
  255.             mx = max_end;
  256.         if(max_end<0)
  257.             max_end=0;
  258.     }
  259.     return mx;
  260. }
  261. ll ncr(ll n, ll r) {
  262.     if (n==r) return 1;
  263.     if(r==1) return n;
  264.     return ncr(n-1, r-1) + ncr(n-1, r);
  265. }
  266.  
  267. ll ncr2(ll n, ll r)
  268. {
  269.     static vll fact;
  270.     static bool initialized = false;
  271.     if (!initialized)
  272.     {
  273.         ll sz = 100LL;
  274.         fact.resize(sz, 1);
  275.         for (ll i = 2; i < sz; i++)
  276.             fact[i] = mod_mul(fact[i - 1], i, MOD);
  277.         initialized = true;
  278.         // cout << "initialized" << nl;
  279.     }
  280.     ll ans = mod_div(fact[n], mod_mul(fact[n - r], fact[r], MOD), MOD);
  281.     return ans;
  282. }
  283. // Returns nCr % p using Fermat's little theorem.
  284. unsigned long long nCrModPFermat(unsigned long long n, int r, int mod)
  285. {
  286.     // If n<r, then nCr should return 0
  287.     if (n < r) return 0;
  288.     if (r == 0) return 1;
  289.     // Fill factorial array so that we can find all factorial of r, n and n-r
  290.     unsigned long long fac[n + 1]; fac[0] = 1;
  291.     for (int i = 1; i <= n; i++) fac[i] = (fac[i - 1] * i) % mod;
  292.     return (fac[n] * mod_inverse(fac[r], mod) % mod * mod_inverse(fac[n - r], mod) % mod) % mod;
  293. }
  294. ll factorial(ll n) {
  295.     return tgamma(n+1);
  296. }
  297. ll lcm(ll a, ll b){
  298.     return (a*b)/gcd(a,b);
  299. }
  300. bool is_prime(ll n) {
  301.     if (n == 1)
  302.         return false;
  303.     ll i = 2;
  304.     while (i*i <= n) {
  305.         if (n % i == 0)
  306.             return false;
  307.         i += 1;
  308.     }
  309.     return true;
  310. }
  311.  
  312. // Sieve of Eratosthenes
  313. vector<bool> sieve(ll n)
  314. {
  315.     vector<bool> is_prime(n+1, true);
  316.     is_prime[0] = is_prime[1] = false;
  317.     for(ll i = 2; i*i<=n; i++)
  318.     {
  319.         if(is_prime[i] == true && (ll)i*i <=n)
  320.         {
  321.             for(int j = i*i; j<=n; j += i)
  322.                 is_prime[j] = false;
  323.         }
  324.     }
  325.     return is_prime;
  326. }
  327.  
  328. // extended euclidean algorithm
  329. ll extEuclid(ll a, ll b, ll& x, ll& y) {
  330.     if (b == 0) {
  331.         x = 1;
  332.         y = 0;
  333.         return a;
  334.     }
  335.     ll x1, y1;
  336.     ll d = extEuclid(b, a % b, x1, y1);
  337.     x = y1;
  338.     y = x1 - y1 * (a / b);
  339.     return d;
  340. }
  341.  
  342. vector<long long> trial_division1(long long n) {
  343.     vector<long long> factorization;
  344.     for (long long d = 2; d * d <= n; d++) {
  345.         while (n % d == 0) {
  346.             factorization.push_back(d);
  347.             n /= d;
  348.         }
  349.     }
  350.     if (n > 1)
  351.         factorization.push_back(n);
  352.     return factorization;
  353. }
  354.  
  355. vll get_factors(ll num, ll upper_limit, bool reset)
  356. {
  357.     vll factors;
  358.     static ll n;
  359.     static vll spf;
  360.     static bool initialized = false;
  361.     if (!initialized || reset)
  362.     {
  363.         n = upper_limit;
  364.         initialized = true;
  365.         spf.assign(n, -1);
  366.         for (ll i = 2; i < n; i++)
  367.             if (spf[i] == -1)
  368.                 for (ll j = i; j < n; j += i)
  369.                     if (spf[j] == -1)
  370.                         spf[j] = i;
  371.     }
  372.  
  373.     if (num <= 1)
  374.         return factors;
  375.     while (num > 1)
  376.     {
  377.         factors.push_back(spf[num]);
  378.         num /= spf[num];
  379.     }
  380.     return factors;
  381. }
  382. /* ------------------------------------------------------ */
  383.  
  384. /* -------------------- BINARY SEARCH ------------------- */
  385.  
  386. /* Compartor function for last_index example */
  387. // bool find(ll mid, ll target)
  388. // {
  389. //     if (mid <= target)
  390. //         return true;
  391. //     else
  392. //         return false;
  393. // }
  394. // Calling : cout << first_index(l, r, v, find, target) << nl;
  395.  
  396. ll last_index(ll l, ll r, vll &v, bool (&comp)(ll, ll), ll target)
  397. {
  398.     while (l < r)
  399.     {
  400.         ll mid = (l + r + 1) / 2; // ceil
  401.         if (comp(v[mid], target)) // if v[mid] <= target
  402.             l = mid;
  403.         else                      // if v[mid] > target
  404.             r = mid - 1;
  405.     }
  406.     return (comp(l, target)) ? l : -1;
  407. }
  408. ll first_index(ll l, ll r, vll &v, bool (&comp)(ll, ll), ll target)
  409. {
  410.     while (l < r)
  411.     {
  412.         ll mid = (l + r) / 2;      // floor
  413.         if (comp(v[mid], target))  // if v[mid] < target
  414.             l = mid + 1;
  415.         else                       // if v[mid] >= target
  416.             r = mid;
  417.     }
  418.     return (comp(l, target)) ? l : -1;
  419. }
  420.  
  421. /* ----------------- BINARY SEARCH ENDS ----------------- */
  422.  
  423.  
Add Comment
Please, Sign In to add comment