Advertisement
sasa2742002

Untitled

Mar 27th, 2023
798
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. #define T     \
  7.   ll rrr;     \
  8.   cin >> rrr; \
  9.   for (ll w1 = 0; w1 < rrr; w1++)
  10. #define cin(vec, a) for (ll i = 0; i < a && cin >> vec[i]; i++)
  11. #define cout(vec, a) for (ll i = 0; i < a && cout << vec[i] << " "; i++)
  12. #define MOD 1000000007
  13. #define PI 3.14159265
  14. #define ceil(a, b) ((a / b) + (a % b ? 1 : 0))
  15. #define all(v) v.begin(), v.end()
  16. #define rall(v) v.rbegin(), v.rend()
  17. #include <iostream>
  18. #define INF 1e9
  19. #define mod 1000000007
  20. #include <string>
  21. #define el '\n'
  22. #define sp ' '
  23. #define loop(n) for (int i = 0; i < n; i++)
  24. typedef long long ll;
  25. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  26. #define multi_ordered_set tree<ll, null_type, greater_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
  27. /*  /////////////    dsu   //////////////
  28. vector<int> parent;
  29. vector<int> ran;
  30.  
  31. void init(int n)
  32. {
  33.   parent[n] = n;
  34.   ran[n] = 0;
  35. }
  36. int find(int n)
  37. {
  38.   if (parent[n] == n)
  39.     return n;
  40.   return parent[n] = find(parent[n]);
  41. }
  42. void union1(int a, int b)
  43. {
  44.   a = find(a);
  45.   b = find(b);
  46.   if (a != b)
  47.   {
  48.     if (ran[a] < ran[b])
  49.       swap(a, b);
  50.  
  51.     parent[b] = a;
  52.     if (ran[a] == ran[b])
  53.       ran[a]++;
  54.   }
  55. }
  56.   /////////////    dsu   //////////////
  57. */
  58. /*  /////////////    sparse_table   //////////////
  59. vector<vector<ll>> sparse_table;
  60. int op1(int a, int b, string s)
  61. {
  62.   if (s == "min")
  63.     return min(a, b);
  64.   else if (s == "max")
  65.     return max(a, b);
  66.   else if (s == "gcd")
  67.     return __gcd(a, b);
  68.   else if (s == "lcm")
  69.     return (a * b) / __gcd(a, b);
  70.   else if (s == "sum")
  71.     return a + b;
  72.   else if (s == "mul")
  73.     return a * b;
  74. }
  75. void full(int n, int k, string s)
  76. {
  77.   for (int i = 1; i < k; i++)
  78.     for (int j = 0; j + (1 << i) <= n; j++)
  79.       sparse_table[i][j] = op1(sparse_table[i - 1][j], sparse_table[i - 1][j + (1 << (i - 1))], s);
  80. }
  81. int op2(int l, int r, int k)
  82. {
  83.   long long sum = 0;
  84.   for (int i = k; i >= 0; i--)
  85.   {
  86.     if ((1 << i) <= r - l + 1)
  87.     {
  88.       sum += sparse_table[i][l];
  89.       l += 1 << i;
  90.     }
  91.   }
  92.   return sum;
  93. }
  94. void init1()
  95. {
  96.  
  97.   int n, q;
  98.   cin >> n;
  99.   int k = log2(n) + 1;
  100.   sparse_table = vector<vector<ll>>(k, vector<ll>(n, 0));
  101.   for (int i = 0; i < n; i++)
  102.     cin >> sparse_table[0][i];
  103.   full(n, k, "sum");
  104.   cin >> q;
  105.   while (q--)
  106.   {
  107.     int l, r;
  108.     cin >> l >> r;
  109.     int len = r - l + 1;
  110.     int k = log2(len);
  111.     cout << op2(l, r, k) << el;
  112.   }
  113.  
  114. }
  115.   /////////////    sparse_table   //////////////
  116. */
  117. /*  /////////////    fenwick_tree   //////////////
  118. class FenwickTree {
  119. private:
  120.     vector<int> tree;
  121.     int n;
  122.  
  123. public:
  124.     FenwickTree(int size) {
  125.         n = size;
  126.         tree.resize(n+1);
  127.     }
  128.  
  129.     void update(int idx, int val) {
  130.         idx++;
  131.         while (idx <= n) {
  132.             tree[idx] += val;
  133.             idx += idx & (-idx);
  134.         }
  135.     }
  136.  
  137.     int query(int idx) {
  138.         idx++;
  139.         int sum = 0;
  140.         while (idx > 0) {
  141.             sum += tree[idx];
  142.             idx -= idx & (-idx);
  143.         }
  144.         return sum;
  145.     }
  146.  
  147.     int rangeQuery(int l, int r) {
  148.         return query(r) - query(l-1);
  149.     }
  150. };
  151. ///////////    fenwick_tree   //////////////
  152. */
  153. void sasa()
  154. {
  155.   ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  156. #ifndef ONLINE_JUDGE
  157.   freopen("input4.txt", "r", stdin), freopen("output4.txt", "w", stdout);
  158. #endif
  159. }
  160. ///////////////////////////////////////// code //////////////////////////////////////////////////////////////////////////
  161. struct sa
  162. {
  163.   ll a, b, c;
  164. };
  165. vector<sa> v;
  166. vector<vector<vector<ll>>> dp;
  167. ll n, w1, w2;
  168. ll mix(ll idx, ll r1, ll r2)
  169. {
  170.   if (idx == v.size())
  171.   {
  172.     ll t1 = __gcd(r1, r2);
  173.     if (t1 != 0 && (r1 / t1) == w1 && (r2 / t1) == w2)
  174.       return 0;
  175.     else
  176.       return INF;
  177.   }
  178.  
  179.   if (dp[idx][r1][r2] != -1)
  180.     return dp[idx][r1][r2];
  181.  
  182.   ll t1 = __gcd(r1, r2);
  183.   if (t1 != 0 && (r1 / t1) == w1 && (r2 / t1) == w2)
  184.     return dp[idx][r1][r2] = 0;
  185.  
  186.   ll ans = INF;
  187.   ans = min(ans, v[idx].c + mix(idx + 1, r1 + v[idx].a, r2 + v[idx].b));
  188.   ans = min(ans, mix(idx + 1, r1, r2));
  189.  
  190.   return dp[idx][r1][r2] = ans;
  191. }
  192. void solve()
  193. {
  194.   cin >> n >> w1 >> w2;
  195.   v = vector<sa>(n);
  196.   dp = vector<vector<vector<ll>>>(n + 1, vector<vector<ll>>(460 + 1, vector<ll>(460, -1)));
  197.   for (ll i = 0; i < n; i++)
  198.   {
  199.     cin >> v[i].a >> v[i].b >> v[i].c;
  200.   }
  201.   ll l = mix(0, 0, 0);
  202.   cout << (l == INF ? -1 : l);
  203. }
  204.  
  205. int main()
  206. {
  207.   sasa();
  208.   ll t = 1, i = 1;
  209.   // cin >> t;
  210.   while (t--)
  211.   {
  212.     // cout << "test #" << i << ":\n";
  213.     solve();
  214.     i++;
  215.     if (!t)
  216.       break;
  217.     cout << "\n";
  218.   }
  219.  
  220.   return 0;
  221. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement