Submission #647075

#	Time	Username	Problem	Language	Result	Execution time	Memory
647075		borgar02	Fishing Game (RMI19_fishing)	C++17	0 / 100	440 ms	111368 KiB

fishing

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 305;
const int Mod = 1e9 + 7;
int dp[N][N][N];
int ct = 0, ii, jj, kk;
/*
i : 0 1 1
j : 1 0 1
k: 1 1 0
*/
int norm(int x) { if(x >= Mod) return x - Mod; return x; }
int res(int i, int j, int k)
{
    if(i < 0 || j < 0 || k < 0) return 0;
    if(dp[i][j][k] != -1) return dp[i][j][k];
    dp[i][j][k] = 0;
    ///1 delete + 2 swaps
    dp[i][j][k] = norm(dp[i][j][k] + res(i, j, k - 1));
    dp[i][j][k] = norm(dp[i][j][k] + res(i, j - 1, k));
    dp[i][j][k] = norm(dp[i][j][k] + res(i - 1, j, k));

    ///2 deletes + 1 swap
    dp[i][j][k] = norm(dp[i][j][k] + res(i - 1, j + 1, k - 2));
    dp[i][j][k] = norm(dp[i][j][k] + res(i + 1, j - 2, k - 1));
    dp[i][j][k] = norm(dp[i][j][k] + res(i - 2, j - 1, k + 1));

    ///3 deletes
    dp[i][j][k] = norm(dp[i][j][k] + res(i - 1, j - 1, k - 1));

    return dp[i][j][k];
}

int r[N];

int main()
{

    int n, t;
    cin >> n >> t;
    for(int i = 1; i <= t; i++) {
        for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            for(int k = 0; k < N; k++)
                dp[i][j][k] = -1;
        dp[0][0][0] = 1;
        for(int i = 1; i < N; i++)
            dp[i][0][0] = dp[0][i][0] = dp[0][0][i] = i * dp[0][0][i - 1] % Mod;
        fill(r, r + N, 0);
        for(int j : {0, 1, 2})
            for(int i = 1, x; i <= 2 * n; i++) {
                cin >> x;
                r[x] |= 1 << j;
            }
        ii = jj = kk = 0;
        for(int i = 1; i <= 3 * n; i++)
            if(r[i] == 6) ii++;
            else if(r[i] == 5) jj++;
            else if(r[i] == 3) kk++;
        cout << res(ii, jj, kk) << "\n";
    }
    return 0;
}

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

• Subtask 1: 0 / 100