fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long 
  3. #define mp make_pair 
  4. #define f(i,n) for(int i=0;i<n;i++) 
  5. #define F first 
  6. #define S second 
  7. #define pb push_back 
  8.  
  9. using namespace std;
  10.  
  11. string s[70];
  12. ll n;
  13. ll cache[70][2];
  14.  
  15. ll dp(ll i, ll j){
  16. 	if(i==n and j==1)
  17. 		return 1;
  18. 	else if(i==n)
  19. 		return 0;
  20. 	if(cache[i][j]!=-1)
  21. 		return cache[i][j];
  22. 	ll res = 0;
  23. 	if(s[i]=="OR"){
  24. 		//  using 1
  25. 		res = res + dp(i+1,1);
  26. 		// using 0
  27. 		res = res + dp(i+1,j);
  28. 	}else{
  29. 		res = res + dp(i+1,j&1);
  30. 		res = res + dp(i+1,0);
  31. 	}
  32. 	cache[i][j] = res;
  33. 	return res;
  34. }
  35.  
  36.  
  37. void test(){
  38. 	cin>>n;
  39. 	f(i,n)cin>>s[i];
  40. 	memset(cache,-1,sizeof(cache));
  41. 	cout<<dp(0,0) + dp(0,1)<<"\n";
  42. }
  43.  
  44. int main(){
  45. 	std::ios::sync_with_stdio(false);
  46. 	cin.tie(0);
  47. 	cout.tie(0);
  48. 	int tests=1;
  49. 	// cin>>tests;
  50. 	while(tests--){
  51. 		test();
  52. 	}
  53. }
  54.  
Success #stdin #stdout 0s 4648KB
comments (?)
stdin
copy 
2
AND
OR
stdout
copy 
5
https://ideone.com/WvtZJR
language:
C++14 (gcc 8.3)
created:
3 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!