답안 #644065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
644065 2022-09-23T17:40:14 Z k_balint31415 Fishing Game (RMI19_fishing) C++14
0 / 100
101 ms 64836 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

int n;
ll dp[202][202][202];

ll calc(int a, int b, int c){
    if(a<0 || b<0 || c<0) return 0;
    if(dp[a][b][c] != -1) return dp[a][b][c];

    ll res=0;
    
    if(a>=2) res+=calc(a-2,b,c)*a %mod*(a-1)%mod*(b+1)%mod,res%=mod;
    if(a>=2 && c>=1) res+=calc(a-1,b,c-1)*a%mod*(a-1)%mod*c%mod,res%=mod;

    if(a>=1 && b>=1 && c>=1) res+=calc(a-1,b-1,c-1)*a%mod*b%mod*c%mod,res%=mod;
    if(a>=1 && c>=2) res+=calc(a,b,c-2)*a%mod*c%mod*(c-1)%mod,res%=mod;

    if(a>=1 && b>=1) res+=calc(a-1,b-1,c+1)*a%mod*b%mod*b%mod,res%=mod;

    if(b>=2) res+=calc(a,b-2,c)*b%mod*(c+1)%mod*(b-1)%mod,res%=mod;
    if(b>=1 && c>=1) res+=calc(a+1,b-1,c-1)*b%mod*(c+1)%mod*c%mod,res%=mod;

    dp[a][b][c]=res;
    return res;
}

int arr[302][2];

void solve(){
    for(int i=1;i<=3*n;i++){
        arr[i][0]=arr[i][1]=-1;
    }
    int a,b,c; a=b=c=0;
    for(int i=0;i<3;i++){
        for(int j=1;j<=2*n;j++){
            int x; cin>>x;
            if(arr[x][0]==-1) arr[x][0]=i;
            else arr[x][1]=i;
        }
    }

    for(int i=1;i<=3*n;i++){
        if((arr[i][0]==0 && arr[i][1]==1) || (arr[i][0]==1 && arr[i][1]==0))++a;
        if((arr[i][0]==0 && arr[i][1]==2) || (arr[i][0]==2 && arr[i][1]==0))++b;
        if((arr[i][0]==2 && arr[i][1]==1) || (arr[i][0]==1 && arr[i][1]==2))++c;
    }

    cout << calc(a,b,c) << '\n';
}

int main(){
    for(int i=0;i<202;i++){
        for(int j=0;j<202;j++){
            for(int k=0;k<202;k++){
                dp[i][j][k]=-1;
            }
        }
    }
    dp[0][0][0]=1;

    int tc;
    cin>>n>>tc;
    while(tc--){
        solve();
    }
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 64716 KB Output isn't correct
2 Incorrect 24 ms 64780 KB Output isn't correct
3 Incorrect 25 ms 64724 KB Output isn't correct
4 Incorrect 30 ms 64796 KB Output isn't correct
5 Incorrect 37 ms 64812 KB Output isn't correct
6 Incorrect 41 ms 64716 KB Output isn't correct
7 Incorrect 59 ms 64816 KB Output isn't correct
8 Incorrect 68 ms 64824 KB Output isn't correct
9 Incorrect 78 ms 64828 KB Output isn't correct
10 Incorrect 101 ms 64836 KB Output isn't correct