Advertisement
Guest User

Untitled

a guest
Jun 25th, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.11 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. void init(){
  22. for(int i=0;i<36;i++){
  23. for(int j=0;j<36;j++){
  24. for(int k=0;k<71;k++){
  25. dp[i][j][k]=0;
  26. }
  27. }
  28. }
  29. dp[0][0][0]=1;
  30. }
  31.  
  32. void solve(){
  33. for(int st=1;st<=n;st++){
  34. for(int num_a=0;num_a<st;num_a++){
  35. for(int num_b=0;num_b<st;num_b++){
  36. int num_c=2*(st-1) - num_a - num_b;
  37. int was=dp[num_a][num_b][num_c];
  38. //ab
  39.  
  40. if(num_a<a_sz && num_b<b_sz && a[num_a]<b[num_b]){
  41. dp[num_a+1][num_b+1][num_c]+=was;
  42. }
  43. //ac
  44. if(num_a<a_sz && num_c<c_sz && a[num_a]<c[num_c]){
  45.  
  46. dp[num_a+1][num_b][num_c+1]+=was;
  47. }
  48. //cb
  49. if(num_c<c_sz && num_b<b_sz && c[num_c]<b[num_b]){
  50.  
  51. dp[num_a][num_b+1][num_c+1]+=was;
  52. }
  53. //cc
  54. if(num_c+1<c_sz){
  55. dp[num_a][num_b][num_c+2]+=was;
  56. }
  57. }
  58. }
  59. }
  60. }
  61.  
  62.  
  63. signed main(){
  64. ios_base::sync_with_stdio(false);
  65. cin.tie(0);
  66.  
  67. cin >> n;
  68. vector<int> uu(2*n,2);
  69. cin >> a_sz;
  70. for(int i=0;i<a_sz;i++){
  71. int tmp;
  72. cin >> tmp;
  73. tmp--;
  74. uu[tmp]=0;
  75. }
  76. cin >> b_sz;
  77. c_sz=2*n - a_sz - b_sz;
  78. for(int i=0;i<b_sz;i++){
  79. int tmp;
  80. cin >> tmp;
  81. tmp--;
  82. uu[tmp]=1;
  83. }
  84. for(int i=0;i<2*n;i++){
  85. if(uu[i]==0){
  86. a.push_back(i+1);
  87. }
  88. if(uu[i]==1){
  89. b.push_back(i+1);
  90. }
  91. if(uu[i]==2){
  92. c.push_back(i+1);
  93. }
  94. }
  95. sort(c.begin(),c.end());
  96. sort(b.begin(),b.end());
  97. sort(a.begin(),a.end());
  98. init();
  99. solve();
  100.  
  101. cout << dp[1][1][2] << endl;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement