답안 #647075

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647075 2022-10-01T14:19:38 Z borgar02 Fishing Game (RMI19_fishing) C++17
0 / 100
440 ms 111368 KB
#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
*/
# 결과 실행 시간 메모리 Grader output
1 Incorrect 69 ms 111336 KB Output isn't correct
2 Incorrect 90 ms 111236 KB Output isn't correct
3 Incorrect 90 ms 111308 KB Output isn't correct
4 Incorrect 98 ms 111216 KB Output isn't correct
5 Incorrect 178 ms 111356 KB Output isn't correct
6 Incorrect 217 ms 111360 KB Output isn't correct
7 Incorrect 242 ms 111308 KB Output isn't correct
8 Incorrect 299 ms 111368 KB Output isn't correct
9 Incorrect 346 ms 111364 KB Output isn't correct
10 Incorrect 440 ms 111368 KB Output isn't correct