답안 #854648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854648 2023-09-28T10:14:34 Z lolismek Fishing Game (RMI19_fishing) C++14
100 / 100
634 ms 55804 KB
#include <iostream>
#include <vector>

#define int long long

using namespace std;

const int NMAX = 100;
const int MOD = 1e9 + 7;

int dp[2 * NMAX + 1][2 * NMAX + 1][2 * NMAX + 1];

void op1(int &mult, int &i, int &j, int &k){
    if(i + k != 0){
        mult = 0;
    }
}

void op2(int &mult, int &i, int &j, int &k){
    mult *= i;
    i--;
}

void op3(int &mult, int &i, int &j, int &k){
    mult *= k;
    k--;
    j++;
}

signed main(){

    int n, t;
    cin >> n >> t;

    dp[0][0][0] = 1;

    for(int sum = 1; sum <= 6 * n; sum++){
        for(int w1 = 0; w1 <= sum && w1 <= 2 * n; w1++){
            for(int w2 = 0; w1 + w2 <= sum && w2 <= 2 * n; w2++){
                int w3 = sum - (w1 + w2);

                if(w1 + w3 > 3 * n || w2 + w3 > 3 * n || w1 + w2 > 3 * n){
                    continue;
                }

                for(int s1 = 1; s1 <= 3; s1++){
                    for(int s2 = 1; s2 <= 3; s2++){
                        for(int s3 = 1; s3 <= 3; s3++){
                            if(s1 != 2 && s2 != 2 && s3 != 2){
                                continue;
                            }

                            int i = w1, j = w2, k = w3, mult = 1;

                            if(s1 == 1){
                                op1(mult, i, j, k);
                            }else if(s1 == 2){
                                op2(mult, i, j, k);
                            }else{
                                op3(mult, i, j, k);
                            }

                            if(s2 == 1){
                                op1(mult, j, k, i);
                            }else if(s2 == 2){
                                op2(mult, j, k, i);
                            }else{
                                op3(mult, j, k, i);
                            }

                            if(s3 == 1){
                                op1(mult, k, i, j);
                            }else if(s3 == 2){
                                op2(mult, k, i, j);
                            }else{
                                op3(mult, k, i, j);
                            }

                            if(mult == 0 || i < 0 || j < 0 || k < 0){
                                continue;
                            }

                            (dp[w1][w2][w3] += (dp[i][j][k] * mult) % MOD) %= MOD;
                        }
                    }
                }
            }
        }
    }

    while(t--){
        vector <bool> a(3 * n, 0);
        vector <bool> b(3 * n, 0);
        vector <bool> c(3 * n, 0);
        for(int i = 1; i <= 2 * n; i++){
            int x;
            cin >> x;
            a[x] = 1;
        }
        for(int i = 1; i <= 2 * n; i++){
            int x;
            cin >> x;
            b[x] = 1;
        }
        for(int i = 1; i <= 2 * n; i++){
            int x;
            cin >> x;
            c[x] = 1;
        }

        int w1 = 0, w2 = 0, w3 = 0;
        for(int i = 1; i <= 3 * n; i++){
            w1 += (a[i] && b[i]);
            w2 += (b[i] && c[i]);
            w3 += (c[i] && a[i]);
        }

        cout << dp[w1][w2][w3] << '\n';
    }

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 7 ms 2648 KB Output is correct
5 Correct 87 ms 14552 KB Output is correct
6 Correct 149 ms 21076 KB Output is correct
7 Correct 226 ms 28240 KB Output is correct
8 Correct 326 ms 36588 KB Output is correct
9 Correct 481 ms 46080 KB Output is correct
10 Correct 634 ms 55804 KB Output is correct