oj.uz

답안 #477909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477909 2021-10-04T15:15:07 Z Alexandruabcde Fishing Game (RMI19_fishing) C++14
100 / 100
 1170 ms 42464 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL MOD = 1000000007;
constexpr int NMAX = 305;

int dp[NMAX][NMAX][NMAX];

void Do (int what, int &i, int &j, int &k, int &coef) {
    if (what == 1) {
        if (i + k != 0)
            coef = 0;

        return;
    }

    if (what == 2) {
        coef *= i;
        -- i;

        return;
    }

    if (what == 3) {
        coef *= k;
        ++ j;
        -- k;
    }
}

bool Check (int i, int j, int k, int coef) {
    return (i >= 0 && j >= 0 && k >= 0 && coef > 0);
}

void Precalculare (int N) {
    dp[0][0][0] = 1;

    for (int Total = 1; Total <= 6 * N; ++ Total )
        for (int comun_ab = 0; comun_ab <= 2*N && comun_ab <= Total; ++ comun_ab)
            for (int comun_bc = 0; comun_bc <= 2*N && comun_bc + comun_ab <= Total; ++ comun_bc) {
                int comun_ac = Total - comun_ab - comun_bc;

                if (comun_ab + comun_bc > 3 * N || comun_ab + comun_ac > 3 * N || comun_bc + comun_ac > 3 * N)
                    continue;

                for (int op_1 = 1; op_1 <= 3; ++ op_1)
                    for (int op_2 = 1; op_2 <= 3; ++ op_2)
                        for (int op_3 = 1; op_3 <= 3; ++ op_3) {
                            int i = comun_ab, j = comun_bc, k = comun_ac;

                            if (op_1 != 2 && op_2 != 2 && op_3 != 2)
                                continue;

                            int coef = 1;

                            Do(op_1, i, j, k, coef);
                            if (!Check(i, j, k, coef)) continue;
                            Do(op_2, j, k, i, coef);
                            if (!Check(i, j, k, coef)) continue;
                            Do(op_3, k, i, j, coef);
                            if (!Check(i, j, k, coef)) continue;

                            dp[comun_ab][comun_bc][comun_ac] = (dp[comun_ab][comun_bc][comun_ac] + 1LL * coef * dp[i][j][k]) % MOD;
                        }
            }
}

int N;

int fr[3][NMAX];

void Read () {
    for (int i = 0; i < 3; ++ i ) {
        for (int j = 1; j <= 2*N; ++ j ) {
            int x;
            cin >> x;

            fr[i][x]++;
        }
    }
}

void Solve () {
    int good[3];
    good[0] = good[1] = good[2] = 0;
    for (int i = 1; i <= 3*N; ++ i ) {
        if (fr[0][i] && fr[1][i]) good[0]++;
        if (fr[1][i] && fr[2][i]) good[1]++;
        if (fr[2][i] && fr[0][i]) good[2]++;

        fr[0][i] = fr[1][i] = fr[2][i] = 0;
    }

    cout << dp[good[0]][good[1]][good[2]] << '\n';
}

void do_Testcase() {
    Read();

    Solve();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    cin >> N >> T;

    Precalculare(N);

    for (; T; -- T ) {
        do_Testcase();
    }

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 10 ms 2228 KB Output is correct
5 Correct 156 ms 11328 KB Output is correct
6 Correct 247 ms 16012 KB Output is correct
7 Correct 406 ms 21584 KB Output is correct
8 Correct 641 ms 28048 KB Output is correct
9 Correct 1061 ms 35216 KB Output is correct
10 Correct 1170 ms 42464 KB Output is correct