Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- //#define int long long
- int dp[36][36][71][4];
- int n;
- int a_sz;
- int b_sz;
- int c_sz;
- //sort
- vector<int> a;
- vector<int> b;
- vector<int> c;
- const int nt=1e9;
- void init(){
- for(int i=0;i<36;i++){
- for(int j=0;j<36;j++){
- for(int k=0;k<71;k++){
- for(int tp=0;tp<4;tp++){
- dp[i][j][k][tp]=0;
- }
- }
- }
- }
- dp[0][0][0][0]=1;
- }
- void solve(){
- for(int st=1;st<=n;st++){
- for(int num_a=0;num_a<st;num_a++){
- for(int num_b=0;num_b<st;num_b++){
- int num_c=2*(st-1) - num_a - num_b;
- for(int tp=0;tp<4;tp++){
- int last_up;
- int last_dw=0;
- if(tp==0){
- last_up=(num_a==0 ? nt : a[num_a-1]);
- last_dw=(num_b==0 ? nt : b[num_b-1]);
- }
- if(tp==1){
- last_up=(num_a==0 ? nt : a[num_a-1]);
- last_dw=(num_c==0 ? nt : c[num_c-1]);
- }
- if(tp==2){
- last_up=(num_b==0 ? nt : b[num_b-1]);
- last_dw=(num_c==0 ? nt : c[num_c-1]);
- }
- if(tp==3){
- if(num_c>2){
- last_dw=c[num_c-2];
- last_up=c[num_c-1];
- }
- else{
- last_dw=nt;
- last_up=nt;
- }
- }
- int was=dp[num_a][num_b][num_c][tp];
- if(st==1){
- last_dw=0;
- last_up=0;
- }
- //ab
- 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){
- dp[num_a+1][num_b+1][num_c][0]+=was;
- }
- //ac
- 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){
- dp[num_a+1][num_b][num_c+1][1]+=was;
- }
- //cb
- 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){
- dp[num_a][num_b+1][num_c+1][2]+=was;
- }
- //cc
- if(num_c+1<c_sz && c[num_c-2]>last_up && c[num_c-1]>last_dw){
- dp[num_a][num_b][num_c+2][3]+=was;
- }
- }
- }
- }
- }
- }
- signed main(){
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cin >> n;
- vector<int> uu(2*n,2);
- cin >> a_sz;
- for(int i=0;i<a_sz;i++){
- int tmp;
- cin >> tmp;
- tmp--;
- uu[tmp]=0;
- }
- cin >> b_sz;
- c_sz=2*n - a_sz - b_sz;
- for(int i=0;i<b_sz;i++){
- int tmp;
- cin >> tmp;
- tmp--;
- uu[tmp]=1;
- }
- for(int i=0;i<2*n;i++){
- if(uu[i]==0){
- a.push_back(i+1);
- }
- if(uu[i]==1){
- b.push_back(i+1);
- }
- if(uu[i]==2){
- c.push_back(i+1);
- }
- }
- sort(c.begin(),c.end());
- sort(b.begin(),b.end());
- sort(a.begin(),a.end());
- init();
- solve();
- int ans=0;
- /*for(int i=0;i<4;i++){
- ans+=dp[a_sz][b_sz][c_sz][i];
- }
- cout << ans << endl;*/
- cout << dp[0][1][1][2] << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement