API tools faq
paste
hitarth_gg

amazonOA Reddit

hitarth_gg
Mar 12th, 2025
195
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.49 KB | None | 0 0
raw download clone embed print report
  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
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!