oj.uz

Submission #283949

# Submission time Handle Problem Language Result Execution time Memory
283949 2020-08-26T10:02:52 Z valerikk Fishing Game (RMI19_fishing) C++17
100 / 100
 469 ms 110460 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int M = 1e9 + 7;
const int N = 3 * 99 + 7;

int n;
int d[N][N][N];
int w[N][2];

int dp(int n01, int n12, int n02) {
    if (~d[n01][n12][n02]) return d[n01][n12][n02];
    if (n01 == 0 && n12 == 0 && n02 == 0) return d[n01][n12][n02] = 1;
    d[n01][n12][n02] = 0;
    for (int a0 = 0; a0 < 3; ++a0) {
        if (a0 == 0 && (n01 > 0 || n02 > 0)) continue;
        if (a0 == 1 && n01 == 0) continue;
        if (a0 == 2 && n02 == 0) continue;
        int m01 = n01, m12 = n12, m02 = n02;
        int p = 1;
        if (a0 == 1) {
            p = (ll)p * m01 % M;
            m01--;
        }
        if (a0 == 2) {
            p = (ll)p * m02 % M;
            m02--;
            m12++;
        }
        for (int a1 = 0; a1 < 3; ++a1) {
            if (a1 == 1 && (m01 > 0 || m12 > 0)) continue;
            if (a1 == 0 && m01 == 0) continue;
            if (a1 == 2 && m12 == 0) continue;
            int k01 = m01, k12 = m12, k02 = m02;
            int q = p;
            if (a1 == 0) {
                q = (ll)q * k01 % M;
                k01--;
                k02++;
            }
            if (a1 == 2) {
                q = (ll)q * m12 % M;
                k12--;
            }
            for (int a2 = 0; a2 < 3; ++a2) {
                if (a2 == 2 && (k12 > 0 || k02 > 0)) continue;
                if (a2 == 0 && k02 == 0) continue;
                if (a2 == 1 && k12 == 0) continue;
                int h01 = k01, h12 = k12, h02 = k02;
                int r = q;
                if (a2 == 0) {
                    r = (ll)r * h02 % M;
                    h02--;
                }
                if (a2 == 1) {
                    r = (ll)r * h12 % M;
                    h12--;
                    h01++;
                }
                if (h01 + h12 + h02 < n01 + n12 + n02) {
                    d[n01][n12][n02] += (ll)dp(h01, h12, h02) * r % M;
                    if (d[n01][n12][n02] >= M) d[n01][n12][n02] -= M;
                }
            }
        }
    }
    return d[n01][n12][n02];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> n >> t;
    while (t--) {
        memset(w, 255, sizeof(w));
        for (int p = 0; p < 3; ++p) {
            for (int i = 0; i < 2 * n; ++i) {
                int a;
                cin >> a;
                a--;
                if (~w[a][0]) w[a][1] = p; else w[a][0] = p;
            }
        }
        int n01 = 0, n12 = 0, n02 = 0;
        for (int i = 0; i < 3 * n; ++i) {
            if (w[i][0] == 0 && w[i][1] == 1) n01++;
            if (w[i][0] == 1 && w[i][1] == 2) n12++;
            if (w[i][0] == 0 && w[i][1] == 2) n02++;
        }
        memset(d, 255, sizeof(d));
        cout << dp(n01, n12, n02) << '\n';
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 110328 KB Output is correct
2 Correct 114 ms 110340 KB Output is correct
3 Correct 116 ms 110400 KB Output is correct
4 Correct 124 ms 110340 KB Output is correct
5 Correct 220 ms 110360 KB Output is correct
6 Correct 251 ms 110328 KB Output is correct
7 Correct 301 ms 110460 KB Output is correct
8 Correct 330 ms 110360 KB Output is correct
9 Correct 418 ms 110308 KB Output is correct
10 Correct 469 ms 110328 KB Output is correct