oj.uz

Submission #305540

# Submission time Handle Problem Language Result Execution time Memory
305540 2020-09-23T13:36:13 Z apostoldaniel854 Fishing Game (RMI19_fishing) C++14
0 / 100
 2000 ms 335224 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int N = 100;
int dp[1 + 3 * N][1 + 3 * N][1 + 3 * N][3][2]; /// A B C : 0/1 done
int freqA[1 + 2 * N], freqB[1 + 2 * N], freqC[1 + 2 * N];

const int MOD = 1e9 + 7;

void add (int &a, int b) {
    a += b;
    if (a >= MOD)
        a -= MOD;
}

int getDp (int ab, int bc, int ca, int turn, bool moved) {
    if (ab + bc + ca == max ({ab, bc, ca})) {
        int ans = 1;
        for (int i = 1; i <= max ({ab, bc, ca}); i++)
            ans = 1ll * ans * i % MOD;
        return ans;
    }
    if (dp[ab][bc][ca][turn][moved]) return dp[ab][bc][ca][turn][moved];
    int ans = 0;
    if (turn == 0) { /// A -> B or A -> C
        if (ab > 0)
            add (ans, getDp (ab - 1, bc, ca, turn + 1, true));
        if (ca > 0)
            add (ans, getDp (ab, bc + 1, ca - 1, turn + 1, moved));
        if (ab == 0 && ca == 0)
            add (ans, getDp (ab, bc, ca, turn + 1, moved));
    }
    if (turn == 1) { /// B -> A or B -> C
        if (bc > 0)
            add (ans, getDp (ab, bc - 1, ca, turn + 1, true));
        if (ab > 0)
            add (ans, getDp (ab - 1, bc, ca + 1, turn + 1, moved));
        if (ab == 0 && bc == 0)
            add (ans, getDp (ab, bc, ca, turn + 1, moved));
    }
    if (turn == 2) { /// C -> B or C -> A
        if (ca > 0)
            add (ans, getDp (ab, bc, ca - 1, 0, 0));
        if (moved) {
            if (bc > 0)
                add (ans, getDp (ab, bc - 1, ca + 1, 0, 0));
            if (ca == 0 && bc == 0)
                add (ans, getDp (ab, bc, ca, 0, 0));
        }
    }
    return dp[ab][bc][ca][turn][moved] = ans;
}

void solveTest (int n) {
    for (int i = 1; i <= 3 * n; i++)
        freqA[i] = freqB[i] = freqC[i] = 0;

    for (int i = 0; i < 2 * n; i++) {
        int x;
        cin >> x;
        freqA[x]++;
    }
    for (int i = 0; i < 2 * n; i++) {
        int x;
        cin >> x;
        freqB[x]++;
    }
    for (int i = 0; i < 2 * n; i++) {
        int x;
        cin >> x;
        freqC[x]++;
    }
    int AB = 0, BC = 0, CA = 0;
    for (int i = 1; i <= 3 * n; i++) {
        if (freqA[i] && freqB[i])
            AB++;
        if (freqB[i] && freqC[i])
            BC++;
        if (freqC[i] && freqA[i])
            CA++;
    }

  ///  dp[AB][BC][CA][0][0] = 1;
    cout << getDp (AB, BC, CA, 0, false) << "\n";
//    int total = AB + BC + CA;
/*    for (int sum = total; sum > 0; sum--)
        for (int ab = 0; ab <= min (AB, sum); ab++)
            for (int bc = 0; bc <= min (BC, sum - ab); bc++) {
                int ca = sum - ab - bc;
                if (ca <= CA) {
                    for (int turn = 0; turn < 3; turn++) {
                        for (int moved = 0; moved < 2; moved++)
                            pushDp (ab, bc, ca, turn, moved);
                    }
                }
            }*/
}

int main () {
    int n, t;
    cin >> n >> t;
    while (t--)
        solveTest (n);
    return 0;
}

/**
    1 1
    1 2
    3 3
    2 1
**/

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Incorrect 1 ms 1152 KB Output isn't correct
4 Incorrect 4 ms 3456 KB Output isn't correct
5 Incorrect 42 ms 21752 KB Output isn't correct
6 Incorrect 64 ms 32632 KB Output isn't correct
7 Incorrect 139 ms 48760 KB Output isn't correct
8 Incorrect 431 ms 119416 KB Output isn't correct
9 Incorrect 1032 ms 220132 KB Output isn't correct
10 Execution timed out 2096 ms 335224 KB Time limit exceeded