fork download
copy 
  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. 		// for(int j = 0; j < m; j++)
  122. 		// {
  123. 		// 	if(s1[i].first + s2[j].first)
  124. 		// 	{
  125.  
  126. 		// 	}
  127. 		// }
  128. 		while(j >= 0 and s1[i].first + s2[j].first >= h)
  129. 		{
  130. 			el++;
  131. 			os.insert({s2[j].second, sz++});
  132. 			// mp[s2[j].second]++;
  133. 			j--;
  134. 		}
  135. 		int ptr2 = j + 1;
  136. 		if(ptr2 == m)
  137. 		{
  138. 			continue;
  139. 		}
  140. 		if(s1[i].second >= h)
  141. 		{
  142. 			ret += el;
  143. 			continue;
  144. 		}
  145. 		int x = h - s1[i].second;
  146. 		int kitnebadey = os.size() - os.order_of_key({x, 0});
  147. 		ret += kitnebadey;
  148. 	}
  149. 	print(ret);
  150. }
  151.  
  152.  
  153. int32_t main()
  154. {	
  155.     ios_base:: sync_with_stdio(false);
  156. 	cin.tie(NULL);
  157. 	cout.tie(NULL);
  158. // 	#ifndef ONLINE_JUDGE
  159. // 	    freopen("input.txt", "r", stdin);
  160. // 	    freopen("output.txt", "w", stdout);
  161. // 	#endif
  162. 	int t = 1;
  163. 	cin >> t;
  164. 	while(t--)solve();
  165. 	return 0;
  166. }
  167.  
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case #1: 1
https://ideone.com/YbdINU
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!