Submission #70473745

Source Code Expand

#include <bits/stdc++.h>

#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint;

int main() {
    int N, X, Y, K, M;
    cin >> N >> X >> Y >> K >> M;
    atcoder::modint::set_mod(M);
    int Z = N - X - Y;
    vector dp(X + 1, vector(Y + 1, vector(Z + 1, vector<mint>(K + 1))));
    dp[0][0][0][0] = 1;
    for (int x = 0; x <= X; x++) {
        for (int y = 0; y <= Y; y++) {
            for (int z = 0; z <= Z; z++) {
                for (int k = 0; k <= K; k++) {
                    if (x + 1 <= X && k + 2 * y + z <= K) {
                        dp[x + 1][y][z][k + 2 * y + z] += dp[x][y][z][k];
                    }
                    if (y + 1 <= Y && k + 2 * z + x <= K) {
                        dp[x][y + 1][z][k + 2 * z + x] += dp[x][y][z][k];
                    }
                    if (z + 1 <= Z && k + 2 * x + y <= K) {
                        dp[x][y][z + 1][k + 2 * x + y] += dp[x][y][z][k];
                    }
                }
            }
        }
    }
    vector comb(N + 1, vector<mint>(N + 1));
    for (int i = 0; i <= N; i++) {
        comb[i][0] = 1;
        for (int j = 1; j < i; j++) comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        comb[i][i] = 1;
    }
    mint ans = 0;
    for (int x = 0; x <= X; x++) {
        for (int y = 0; y <= Y; y++) {
            for (int z = 0; z <= Z; z++) {
                for (int k = 0; k <= K; k++) {
                    int p = x + y + z, q = N - p;
                    if (K - k - p * q < 0) continue;
                    ans += comb[N][x + y + z] * dp[x][y][z][k] * dp[X - x][Y - y][Z - z][K - k - p * q];
                }
            }
        }
    }
    cout << ans.val() << "\n";
}

Submission Info

Submission Time
Task C - Sum of Three Inversions
User otoshigo
Language C++ 20 (gcc 12.2)
Score 100
Code Size 1748 Byte
Status AC
Exec Time 201 ms
Memory 87428 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 38
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-random-01.txt, 01-random-02.txt, 02-random-01.txt, 02-random-02.txt, 03-random-01.txt, 04-random-01.txt, 04-random-02.txt, 05-random-01.txt, 05-random-02.txt, 05-random-03.txt, 06-random-01.txt, 06-random-02.txt, 06-random-03.txt, 07-random-01.txt, 07-random-02.txt, 07-random-03.txt, 08-random-01.txt, 08-random-02.txt, 08-random-03.txt, 08-random-04.txt, 08-random-05.txt, 09-random-01.txt, 09-random-02.txt, 09-random-03.txt, 10-random-01.txt, 10-random-02.txt, 10-random-03.txt, 11-random-01.txt, 11-random-02.txt, 11-random-03.txt, 11-random-04.txt, 12-handmade.txt, 13-handmade.txt, 14-handmade-01.txt, 14-handmade-02.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-random-01.txt AC 1 ms 3708 KiB
01-random-02.txt AC 1 ms 3484 KiB
02-random-01.txt AC 46 ms 24640 KiB
02-random-02.txt AC 51 ms 26144 KiB
03-random-01.txt AC 1 ms 3556 KiB
04-random-01.txt AC 2 ms 4176 KiB
04-random-02.txt AC 63 ms 29344 KiB
05-random-01.txt AC 12 ms 8776 KiB
05-random-02.txt AC 5 ms 6956 KiB
05-random-03.txt AC 6 ms 6124 KiB
06-random-01.txt AC 1 ms 3592 KiB
06-random-02.txt AC 1 ms 3480 KiB
06-random-03.txt AC 1 ms 3568 KiB
07-random-01.txt AC 2 ms 3888 KiB
07-random-02.txt AC 1 ms 3560 KiB
07-random-03.txt AC 3 ms 4728 KiB
08-random-01.txt AC 22 ms 14804 KiB
08-random-02.txt AC 48 ms 24652 KiB
08-random-03.txt AC 2 ms 4608 KiB
08-random-04.txt AC 46 ms 24256 KiB
08-random-05.txt AC 18 ms 12520 KiB
09-random-01.txt AC 1 ms 3644 KiB
09-random-02.txt AC 1 ms 3892 KiB
09-random-03.txt AC 1 ms 3768 KiB
10-random-01.txt AC 6 ms 6100 KiB
10-random-02.txt AC 4 ms 6288 KiB
10-random-03.txt AC 4 ms 5136 KiB
11-random-01.txt AC 68 ms 33444 KiB
11-random-02.txt AC 17 ms 10300 KiB
11-random-03.txt AC 70 ms 34196 KiB
11-random-04.txt AC 62 ms 29756 KiB
12-handmade.txt AC 70 ms 34416 KiB
13-handmade.txt AC 1 ms 3560 KiB
14-handmade-01.txt AC 201 ms 87428 KiB
14-handmade-02.txt AC 72 ms 35284 KiB
sample-01.txt AC 1 ms 3636 KiB
sample-02.txt AC 1 ms 3660 KiB
sample-03.txt AC 45 ms 24244 KiB