fork(1) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Case #1: 59031
Case #2: 59031
Case #3: 59031
Case #4: 59031
Case #5: 59031
Case #6: 59031
Case #7: 59031
https://ideone.com/4OKDA4
language:
C++14 (gcc 8.3)
created:
5 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!