jiteshrao

Untitled

Oct 19th, 2019
35
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace __gnu_pbds;
  6. using namespace std;
  7.  
  8.  
  9. #define FOR(i, x, n) for(ll i = x; i < n; i++)
  10. #define pb push_back
  11. #define pf push_front
  12. #define ll long long
  13. #define hii cout << "hii" << endl
  14. #define pii pair<int, int>
  15. #define pll pair<ll, ll>
  16. #define int ll
  17. #define mpp make_pair
  18. #define endl '\n'
  19. #define ff first
  20. #define ss second
  21. #define vi vector<int>
  22. #define all(s) s.begin(), s.end()
  23. #define si size()
  24.  
  25. template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
  26. template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
  27. template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
  28. template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
  29.  
  30.  
  31. #ifndef ONLINE_JUDGE
  32. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  33.     template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
  34.     template <class Arg1, class... Args>
  35.     void __f(const char* names, Arg1&& arg1, Args&&... args) {
  36.         const char* sep = strchr(names + 1, ',');
  37.         cerr.write(names, sep - names) << " : " << arg1 << "  ";
  38.         __f(sep + 1, args...);
  39.     }
  40. #else
  41. #define trace(...) 0
  42. #pragma GCC optimize ("O3")
  43. #pragma GCC optimize ("unroll-loops")
  44. #pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  45. #define _CRT_SECURE_NO_WARNINGS
  46. #endif // ifndef ONLINE_JUDGE
  47.  
  48.  
  49. typedef
  50. tree<
  51.   pair<int,int>,
  52.   null_type,
  53.   less<pair<int,int>>,
  54.   rb_tree_tag,
  55.   tree_order_statistics_node_update>
  56. ordered_set;
  57.  
  58.  
  59. const int N = 1 << 12;
  60. const int mod = 1e9 + 7;
  61. int query = 1;
  62. vector<pii> s1, s2;
  63. int arr[22];
  64. int brr[22];
  65. int n, h;
  66. void print(int ret)
  67. {
  68.     cout << "Case #" << query++ << ": " << ret << endl;
  69. }
  70.  
  71.  
  72.  
  73. void f(int idx, int cnt1, int cnt2)
  74. {
  75.     if(idx == n / 2)
  76.     {
  77.         s1.push_back({cnt1,cnt2});
  78.         return;
  79.     }
  80.     f(idx + 1, cnt1 + arr[idx], cnt2);
  81.     f(idx + 1, cnt1, cnt2 + brr[idx]);
  82.     f(idx + 1, cnt1 + arr[idx], cnt2 + brr[idx]);
  83. }
  84. void g(int idx, int cnt1, int cnt2)
  85. {
  86.     if(idx == n)
  87.     {
  88.         s2.push_back({cnt1,cnt2});
  89.         return;
  90.     }
  91.     g(idx + 1, cnt1 + arr[idx], cnt2);
  92.     g(idx + 1, cnt1, cnt2 + brr[idx]);
  93.     g(idx + 1, cnt1 + arr[idx], cnt2 + brr[idx]);
  94. }
  95.  
  96. void solve()
  97. {
  98.     s1.clear();
  99.     s2.clear();
  100.     cin >> n >> h;
  101.     for(int i = 0; i < n; i++)
  102.     {
  103.         cin >> arr[i];
  104.     }
  105.     for(int i = 0; i < n; i++)
  106.     {
  107.         cin >> brr[i];
  108.     }
  109.     f(0, 0, 0);
  110.     g(n / 2, 0, 0);
  111.     int n = s1.size(), m = s2.size();
  112.     sort(all(s1));
  113.     sort(all(s2));
  114.     int j = m - 1;
  115.     int ret = 0;
  116.     ordered_set os;
  117.     int el = 0;
  118.     int sz = 0;
  119.     for(int i = 0; i < n; i++)
  120.     {
  121.         while(j >= 0 and s1[i].first + s2[j].first >= h)
  122.         {
  123.             el++;
  124.             os.insert({s2[j].second, sz++});
  125.             j--;
  126.         }
  127.         int ptr2 = j + 1;
  128.         if(ptr2 == m)
  129.         {
  130.             continue;
  131.         }
  132.         if(s1[i].second >= h)
  133.         {
  134.             ret += el;
  135.             continue;
  136.         }
  137.         int x = h - s1[i].second;
  138.         int kitnebadey = os.size() - os.order_of_key({x, 0});
  139.         ret += kitnebadey;
  140.     }
  141.     print(ret);
  142. }
  143.  
  144.  
  145. int32_t main()
  146. {  
  147.     ios_base:: sync_with_stdio(false);
  148.     cin.tie(NULL);
  149.     cout.tie(NULL);
  150.     int t = 1;
  151.     cin >> t;
  152.     while(t--)solve();
  153.     return 0;
  154. }
RAW Paste Data