Sreekar_0125

Untitled

Oct 19th, 2024
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.19 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. template <class T>
  8. using pbds =
  9. tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10. #define cerr if(false)cerr
  11. #define int long long
  12. #define pb push_back
  13. #define F first
  14. #define S second
  15. #define yes cout << "Yes\n"
  16. #define no cout << "No\n"
  17. #define yn(x) x ? yes : no
  18. #define f(i, s, e) for (int i = s; i < e; i++)
  19. #define vi vector<int>
  20. #define vb vector<bool>
  21. #define pii pair<int, int>
  22. #define vpi vector<pii>
  23. #define all(x) x.begin(), x.end()
  24. #define minele(x) *min_element(all(x))
  25. #define maxele(x) *max_element(all(x))
  26. #define endl '\n'
  27. #define in(v, x) binary_search(all(v), x)
  28.  
  29. const int N = 2e5;
  30. const int MOD = 1e9 + 7;
  31. const int inf = LLONG_MAX;
  32. const int minf = LLONG_MIN;
  33.  
  34. #ifndef ONLINE_JUDGE
  35. #define debug(x)            \
  36.     cerr << (#x) << " is "; \
  37.     _print(x)
  38. #define dbg(x...)           \
  39.     cerr << (#x) << " is "; \
  40.     _print(x)
  41. #else
  42. #define debug(x)
  43. #define dbg(x)
  44. #define dbg(x...)
  45. #endif
  46.  
  47. template <typename T>
  48. void _print(T a) {
  49.     cerr << a;
  50. }
  51. template <typename T1, typename... T2>
  52. void _print(T1 t1, T2... t2) {
  53.     cerr << t1 << ", ";
  54.     _print(t2...);
  55.     cerr << endl;
  56. }
  57. template <typename T>
  58. void print(T a) {
  59.     cout << a << ' ';
  60. }
  61. template <typename T>
  62. void println(T a) {
  63.     cout << a << endl;
  64. }
  65. template <class T>
  66. istream &operator>>(istream &is, vector<T> &a) {
  67.     for (auto &x : a) is >> x;
  68.     return is;
  69. }
  70. template <class T>
  71. ostream &operator<<(ostream &os, const vector<T> &a) {
  72.     for (const auto &x : a) os << x << ' ';
  73.     return os;
  74. }
  75.  
  76. template <class T, class V>
  77. void _print(pair<T, V> p);
  78. template <class T>
  79. void _print(vector<T> v);
  80. template <class T>
  81. void _print(set<T> v);
  82. template <class T, class V>
  83. void _print(map<T, V> v);
  84. template <class T>
  85. void _print(multiset<T> v);
  86. template <class T, class V>
  87. void _print(pair<T, V> p) {
  88.     cerr << "{";
  89.     _print(p.F);
  90.     cerr << ",";
  91.     _print(p.S);
  92.     cerr << "} ";
  93. }
  94. template <class T>
  95. void _print(vector<T> v) {
  96.     cerr << "[ ";
  97.     for (T i : v) {
  98.         _print(i);
  99.         cerr << " ";
  100.     }
  101.     cerr << "]";
  102.     cerr << endl;
  103. }
  104. template <class T>
  105. void _print(set<T> v) {
  106.     cerr << "[ ";
  107.     for (T i : v) {
  108.         _print(i);
  109.         cerr << " ";
  110.     }
  111.     cerr << "]";
  112.     cerr << endl;
  113. }
  114. template <class T>
  115. void _print(multiset<T> v) {
  116.     cerr << "[ ";
  117.     for (T i : v) {
  118.         _print(i);
  119.         cerr << " ";
  120.     }
  121.     cerr << "]";
  122.     cerr << endl;
  123. }
  124. template <class T, class V>
  125. void _print(map<T, V> v) {
  126.     cerr << "[ ";
  127.     for (auto i : v) {
  128.         _print(i);
  129.         cerr << " ";
  130.     }
  131.     cerr << "]";
  132.     cerr << endl;
  133. }
  134. template <class T, class V>
  135. void _print(unordered_map<T, V> v) {
  136.     cerr << "[ ";
  137.     for (auto i : v) {
  138.         _print(i);
  139.         cerr << " ";
  140.     }
  141.     cerr << "]";
  142.     cerr << endl;
  143. }
  144.  
  145. void fast() {
  146.     ios_base::sync_with_stdio(false);
  147.     cin.tie(NULL);
  148.     cout.tie(NULL);
  149. }
  150.  
  151. void init_code() {
  152. #ifndef ONLINE_JUDGE
  153.     freopen("input.txt", "r", stdin);
  154.     freopen("output.txt", "w", stdout);
  155.     freopen("error.txt", "w", stderr);
  156. #endif  // ONLINE_JUDGE
  157. }
  158.  
  159. int lcm(int a, int b) { return a * b / __gcd(a, b); }
  160.  
  161. int ops(int from, int to) {
  162.     if (to >= from) return to - from;
  163.     // from > to
  164.     int nxt = ((from + to - 1) / to) * to;
  165.     return nxt - from;
  166. }
  167.  
  168. vector<vi> vals;
  169. int n;
  170.  
  171. int fun(vi &v, int i, bool a, bool b, bool c,
  172.         vector<vector<vector<vector<int>>>> &dp) {
  173.     if (i == n) {
  174.         if (a & b & c)
  175.             return 0;
  176.         else
  177.             return 1e18;
  178.     }
  179.     if (dp[i][a][b][c] != -1) return dp[i][a][b][c];
  180.     return dp[i][a][b][c] = min({fun(v, i + 1, a, b, c, dp),
  181.                                  vals[i][0] + fun(v, i + 1, 1, b, c, dp),
  182.                                  vals[i][1] + fun(v, i + 1, a, 1, c, dp),
  183.                                  vals[i][2] + fun(v, i + 1, a, b, 1, dp),
  184.                                  vals[i][3] + fun(v, i + 1, 1, 1, c, dp),
  185.                                  vals[i][4] + fun(v, i + 1, a, 1, 1, dp),
  186.                                  vals[i][5] + fun(v, i + 1, 1, b, 1, dp),
  187.                                  vals[i][6] + fun(v, i + 1, 1, 1, 1, dp)});
  188. }
  189.  
  190. void solve() {
  191.     int a, b, c;
  192.     cin >> n >> a >> b >> c;
  193.  
  194.     vi v(n);
  195.     cin >> v;
  196.     debug(v);
  197.     vector<vector<vector<vector<int>>>> dp(n, vector<vector<vector<int>>>(2, vector<vector<int>>(2, vector<int>(2, -1))));
  198.  
  199.     // a, b, c, lc(a,b), lc(b,c), lc(c, a);
  200.     int lab = lcm(a, b);
  201.     int lbc = lcm(b, c);
  202.     int lca = lcm(c, a);
  203.     int labc = lcm(a, lcm(b, c));
  204.  
  205.     vals.assign(n, vi(7));
  206.  
  207.     for (int i = 0; i < n; i++) {
  208.         vals[i] = {ops(v[i], a),   ops(v[i], b),   ops(v[i], c),
  209.                    ops(v[i], lab), ops(v[i], lbc), ops(v[i], lca),
  210.                    ops(v[i], labc)};
  211.     }
  212.     debug(vals);
  213.     cout << fun(v, 0, 0, 0, 0, dp) << endl;
  214. }
  215.  
  216. signed main() {
  217.     // init_code();
  218.     fast();
  219.     int t = 1;
  220.     cin >> t;
  221.     while (t--) {
  222.         solve();
  223.     }
  224.     return 0;
  225. }
  226.  
Advertisement
Add Comment
Please, Sign In to add comment