fork download
  1.  
  2. #include <bits/stdc++.h>
  3. #define pb push_back
  4. #define fastIO ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  5. #define PI 3.141592653589793238462643383
  6. #define mp make_pair
  7. #define ff first
  8. #define ss second
  9. #define endl "\n"
  10. #define all(v) v.begin(),v.end()
  11. #define int long long
  12.  
  13. using namespace std;
  14. typedef pair<int,int> pii;
  15. typedef pair<long double,long double>pdd;
  16. template<class T>
  17. using max_pq = priority_queue<T>;
  18. template<class T>
  19. using min_pq = priority_queue<T,vector<T>,greater<T> >;
  20.  
  21. vector<string> split(const string& s, char c) {
  22. vector<string> v; stringstream ss(s); string x;
  23. while (getline(ss, x, c)) v.emplace_back(x); return move(v);
  24. }
  25. template<typename T, typename... Args>
  26. inline string arrStr(T arr, int n) {
  27. stringstream s; s << "[";
  28. for(int i = 0; i < n - 1; i++) s << arr[i] << ",";
  29. if(n > 0)
  30. s << arr[n - 1] ;
  31. s<< "]";
  32. return s.str();
  33. }
  34. #define TRACE
  35. #ifdef TRACE
  36. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  37. template <typename Arg1>
  38. void __f(const char* name, Arg1&& arg1){
  39. cerr << name << " : " << arg1 << endl;
  40. }
  41. template <typename Arg1, typename... Args>
  42. void __f(const char* names, Arg1&& arg1, Args&&... args){
  43. const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  44. }
  45. #else
  46. #define trace(...)
  47. #endif
  48. const int N=20,MAXN=250000,INF=1e18;
  49.  
  50. int sz,h,arr1[N],arr2[N];
  51. vector<int> t[4*MAXN];
  52. vector<pii> v1,v2;
  53.  
  54. void brute(int day, int n, vector<pii> &v, int h1, int h2)
  55. {
  56. if(day==n+1)
  57. {
  58. v.pb({h1,h2});
  59. return;
  60. }
  61. brute(day+1,n,v,h1+arr1[day],h2);
  62. brute(day+1,n,v,h1,h2+arr2[day]);
  63. brute(day+1,n,v,h1+arr1[day],h2+arr2[day]);
  64. }
  65.  
  66.  
  67. void build(vector<pii> a, int v, int tl, int tr) {
  68. if (tl == tr) {
  69. t[v] = vector<int>(1, a[tl].ss);
  70. } else {
  71. int tm = (tl + tr) / 2;
  72. build(a, v*2, tl, tm);
  73. build(a, v*2+1, tm+1, tr);
  74. merge(t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(),
  75. back_inserter(t[v]));
  76. }
  77. }
  78.  
  79. int query(int v, int tl, int tr, int l, int r, int x) {
  80. if (l > r)
  81. return 0;
  82. if (l == tl && r == tr) {
  83. auto pos = lower_bound(t[v].begin(), t[v].end(), x);
  84. return (t[v].end()-pos);
  85. }
  86. int tm = (tl + tr) / 2;
  87. return query(v*2, tl, tm, l, min(r, tm), x)+ query(v*2+1, tm+1, tr, max(l, tm+1), r, x);
  88. }
  89.  
  90. int32_t main()
  91. {
  92. #ifndef ONLINE_JUDGE
  93. freopen("input.txt", "r", stdin);
  94. freopen("output.txt", "w", stdout);
  95. freopen("debug.txt", "w", stderr);
  96. #endif
  97.  
  98. fastIO;
  99.  
  100. int testcases;cin>>testcases;
  101. for(int test=1;test<=testcases;test++)
  102. {
  103. cin>>sz>>h;
  104. memset(t,0,sizeof(t));
  105. for(int i=1;i<=sz;i++)
  106. {
  107. cin>>arr1[i];
  108. }
  109. for(int i=1;i<=sz;i++)
  110. {
  111. cin>>arr2[i];
  112. }
  113. int n=sz/2;
  114. int m=sz-n;
  115. v1.clear();v2.clear();
  116. brute(1,n,v1,0,0);
  117. brute(n+1,sz,v2,0,0);
  118. sort(all(v2));
  119. build(v2,1,0,v2.size()-1);
  120. int ans=0;
  121. for(int i=0;i<v1.size();i++)
  122. {
  123. int r=v2.size()-1;
  124. auto it=lower_bound(all(v2),pii(h-v1[i].ff,0));
  125. int l=(it-v2.begin());
  126. int tmp=query(1,0,v2.size()-1,l,r,h-v1[i].ss);
  127. if(tmp!=INF)
  128. {
  129. ans+=tmp;
  130. }
  131. }
  132. cout<<"Case #"<<test<<": "<<ans<<endl;
  133. }
  134.  
  135. return 0;
  136. }
  137.  
Success #stdin #stdout 0.02s 27152KB
stdin
7
10 3
1 2 2 3 5 3 4 5 1 3
3 3 2 3 5 3 4 5 1 3
10 3
1 2 2 3 5 3 4 5 1 3
3 3 2 3 5 3 4 5 1 3
10 3
1 2 2 3 5 3 4 5 1 3
3 3 2 3 5 3 4 5 1 3
10 3
1 2 2 3 5 3 4 5 1 3
3 3 2 3 5 3 4 5 1 3
10 3
1 2 2 3 5 3 4 5 1 3
3 3 2 3 5 3 4 5 1 3
10 3
1 2 2 3 5 3 4 5 1 3
3 3 2 3 5 3 4 5 1 3
10 3
1 2 2 3 5 3 4 5 1 3
3 3 2 3 5 3 4 5 1 3
stdout
Case #1: 59031
Case #2: 59031
Case #3: 59031
Case #4: 59031
Case #5: 59031
Case #6: 59031
Case #7: 59031