Advertisement
Guest User

Untitled

a guest
Jun 25th, 2018
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.70 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7.  
  8. //#define int long long
  9.  
  10. int dp[36][36][71][4];
  11.  
  12. int n;
  13. int a_sz;
  14. int b_sz;
  15. int c_sz;
  16. //sort
  17. vector<int> a;
  18. vector<int> b;
  19. vector<int> c;
  20.  
  21. const int nt=1e9;
  22.  
  23. void init(){
  24. for(int i=0;i<36;i++){
  25. for(int j=0;j<36;j++){
  26. for(int k=0;k<71;k++){
  27. for(int tp=0;tp<4;tp++){
  28. dp[i][j][k][tp]=0;
  29. }
  30.  
  31. }
  32. }
  33. }
  34. dp[0][0][0][0]=1;
  35. }
  36.  
  37. void solve(){
  38. for(int st=1;st<=n;st++){
  39. for(int num_a=0;num_a<st;num_a++){
  40. for(int num_b=0;num_b<st;num_b++){
  41. int num_c=2*(st-1) - num_a - num_b;
  42. for(int tp=0;tp<4;tp++){
  43. int last_up;
  44. int last_dw=0;
  45. if(tp==0){
  46. last_up=(num_a==0 ? nt : a[num_a-1]);
  47. last_dw=(num_b==0 ? nt : b[num_b-1]);
  48. }
  49. if(tp==1){
  50. last_up=(num_a==0 ? nt : a[num_a-1]);
  51. last_dw=(num_c==0 ? nt : c[num_c-1]);
  52. }
  53. if(tp==2){
  54. last_up=(num_b==0 ? nt : b[num_b-1]);
  55. last_dw=(num_c==0 ? nt : c[num_c-1]);
  56. }
  57. if(tp==3){
  58. if(num_c>2){
  59. last_dw=c[num_c-2];
  60. last_up=c[num_c-1];
  61. }
  62. else{
  63. last_dw=nt;
  64. last_up=nt;
  65. }
  66. }
  67. int was=dp[num_a][num_b][num_c][tp];
  68. if(st==1){
  69. last_dw=0;
  70. last_up=0;
  71. }
  72. //ab
  73. if(num_a<a_sz && num_b<b_sz && a[num_a]<b[num_b] && a[num_a]>last_up && b[num_b]>last_dw){
  74. dp[num_a+1][num_b+1][num_c][0]+=was;
  75. }
  76. //ac
  77. if(num_a<a_sz && num_c<c_sz && a[num_a]<c[num_c] && a[num_a]>last_up && c[num_c]>last_dw){
  78.  
  79. dp[num_a+1][num_b][num_c+1][1]+=was;
  80. }
  81. //cb
  82. if(num_c<c_sz && num_b<b_sz && c[num_c]<b[num_b] && c[num_c]>last_up && b[num_b]>last_dw){
  83.  
  84. dp[num_a][num_b+1][num_c+1][2]+=was;
  85. }
  86. //cc
  87. if(num_c+1<c_sz && c[num_c-2]>last_up && c[num_c-1]>last_dw){
  88. dp[num_a][num_b][num_c+2][3]+=was;
  89. }
  90. }
  91. }
  92. }
  93. }
  94. }
  95.  
  96.  
  97. signed main(){
  98. ios_base::sync_with_stdio(false);
  99. cin.tie(0);
  100.  
  101. cin >> n;
  102. vector<int> uu(2*n,2);
  103. cin >> a_sz;
  104. for(int i=0;i<a_sz;i++){
  105. int tmp;
  106. cin >> tmp;
  107. tmp--;
  108. uu[tmp]=0;
  109. }
  110. cin >> b_sz;
  111. c_sz=2*n - a_sz - b_sz;
  112. for(int i=0;i<b_sz;i++){
  113. int tmp;
  114. cin >> tmp;
  115. tmp--;
  116. uu[tmp]=1;
  117. }
  118. for(int i=0;i<2*n;i++){
  119. if(uu[i]==0){
  120. a.push_back(i+1);
  121. }
  122. if(uu[i]==1){
  123. b.push_back(i+1);
  124. }
  125. if(uu[i]==2){
  126. c.push_back(i+1);
  127. }
  128. }
  129. sort(c.begin(),c.end());
  130. sort(b.begin(),b.end());
  131. sort(a.begin(),a.end());
  132. init();
  133. solve();
  134.  
  135. int ans=0;
  136.  
  137. /*for(int i=0;i<4;i++){
  138. ans+=dp[a_sz][b_sz][c_sz][i];
  139. }
  140. cout << ans << endl;*/
  141. cout << dp[0][1][1][2] << endl;
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement