Guest User

Untitled

a guest
Oct 19th, 2019
50
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. const int mod = 1000000007;
  6. const int N = 500005;
  7. const int LG = 21;
  8. int n,h;
  9. int arr[50];
  10. int brr[50];
  11. int32_t main() {
  12.    
  13.     ios_base::sync_with_stdio(false);
  14.     cin.tie(NULL);
  15.     cout.tie(NULL);
  16.     int t;
  17.     cin >> t;
  18.     for (int tt = 1;tt<=t;tt++) {
  19.         cout<<"Case #"<<tt<<": ";
  20.         int n,h;
  21.         cin >> n >> h;
  22.         int count =0;
  23.         int dp[1ll<<n];
  24.         int val1[1ll<<n];
  25.         int val2[1ll<<n];
  26.         memset(dp,0,sizeof(dp));
  27.         memset(val1,0,sizeof(val1));
  28.         memset(val2,0,sizeof(val2));
  29.         for(int i=0;i<n;i++){
  30.             cin >> arr[i];
  31.         }
  32.         for(int i=0;i<n;i++){
  33.             cin >> brr[i];
  34.         }
  35.         for(int i=0;i<(1ll<<n);i++){
  36.             for(int j=n-1;j>=0;j--){
  37.                 if(i&(1ll<<j))
  38.                     val1[i] += brr[j];
  39.                 else
  40.                     val2[i] += brr[j];
  41.                
  42.             }
  43.         }
  44.         for(int i=0;i<(1ll<<n);i++){
  45.             if(val1[i] >= h)
  46.                 dp[i]++;
  47.         }
  48.         for(int i=0;i<n;i++){
  49.             for(int j=0;j<(1ll<<n);j++){
  50.                 if(j & (1ll<<i)){
  51.                     if(val1[j ^ (1ll<<i)] + val2[j] >= h)
  52.                         dp[j]++;
  53.                 }
  54.             }
  55.         }
  56.  
  57.         for(int i=0;i<(1ll<<n);i++){
  58.             int ha=0;
  59.             for(int j=n-1;j>=0;j--){
  60.                 if(i&(1ll<<j))
  61.                     ha += arr[j];
  62.             }
  63.             if(ha >= h )
  64.                 count += dp[i];
  65.         }
  66.         cout<<count<<"\n";
  67.     }
  68.     return 0;
  69. }
RAW Paste Data