fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define rep(i,a,b) for(int i=a;i<b;i++)
  3. #define rrep(i,b,a) for(int i=b;i>=a;i--)
  4. #define fori(a) for(auto i : a )
  5. #define all(a) begin(a), end(a)
  6. #define set(a,b) memset(a,b,sizeof(a))
  7. #define pi 3.14159
  8. #define ll long long 
  9. #define ull unsigned long long
  10. #define pb push_back
  11. #define PF push_front //deque
  12. // #define mp make_pair
  13. #define pq priority_queue
  14. #define mod 1000000007
  15. #define f first
  16. #define s second
  17. #define pii pair< int, int >
  18. #define tc int t; cin >> t; while(t--)
  19.  
  20. using namespace std;
  21. string repeat(string s, int n) {
  22.     string s1 = s; 
  23.     for (int i=1; i<n;i++) 
  24.         s += s1;
  25.     return s; 
  26. }
  27. string getString(char x) {
  28.     string s(1, x); 
  29.     return s;    
  30. } 
  31.  
  32. void optimizeIO(){
  33.     ios_base::sync_with_stdio(false); 
  34.     cin.tie(NULL);
  35.     cout.tie(NULL);
  36. }
  37. void recursion(ll n,ll h,ll idx,ll a[],ll b[],ll &ans,ll x,ll y,ll s1[],ll s2[]){
  38.     if(x>=h && y>=h){
  39.         ans+=pow(3,n-idx);
  40.         return;
  41.     }
  42.     if(idx==n) return;
  43.     if(x+s1[idx]<h || y+s2[idx]<h) return ;
  44.  
  45.     recursion(n,h,idx+1,a,b,ans,x+a[idx],y,s1,s2);
  46.     recursion(n,h,idx+1,a,b,ans,x,y+b[idx],s1,s2);
  47.     recursion(n,h,idx+1,a,b,ans,x+a[idx],y+b[idx],s1,s2);
  48. }
  49. int main(){
  50.     optimizeIO();
  51.     int lu=1;
  52.     tc{ 
  53.         ll ans=0;
  54.         ll n,h;
  55.         cin>>n>>h;
  56.         ll a[n],b[n];
  57.         rep(i,0,n) cin>>a[i];
  58.         rep(i,0,n) cin>>b[i];
  59.         ll s1[n],s2[n];
  60.         s1[n-1]=a[n-1];
  61.         s2[n-1]=b[n-1];
  62.         rrep(i,n-2,0){
  63.             s1[i]=a[i]+s1[i+1];
  64.             s2[i]=b[i]+s2[i+1];
  65.         }
  66.  
  67.         recursion(n,h,0,a,b,ans,0,0,s1,s2);
  68.         cout<<"Case #"<<lu++<<": "<<ans<<endl;
  69.     }
  70.     return 0;
  71. }
Success #stdin #stdout 0s 4260KB
comments (?)
stdin
copy 
2
2 3
1 2
3 3
2 5
2 2
10 30
stdout
copy 
Case #1: 3
Case #2: 0
https://ideone.com/6lE9NM
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!