QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583747#8820. Exchanging Kubic 2hhoppitreeWA 1ms8108kbC++171.4kb2024-09-22 21:57:342024-09-22 21:57:35

Judging History

你现在查看的是最新测评结果

  • [2024-09-22 21:57:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8108kb
  • [2024-09-22 21:57:34]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 405, M = 805, P = 998244353;

int vis[N][M], f[N][M][N][2];

signed main() {
    int n, m = 0; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int S; scanf("%d", &S);
        for (int j = 1, x; j <= S; ++j) {
            scanf("%d", &x), vis[i][x] = 1;
            m = max(m, x);
        }
    }
    for (int i = 0; i <= m; ++i) {
        f[1][i][n][0] = 1;
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= m; ++j) if (vis[i][j]) {
            for (int k = 0; k <= n; ++k) {
                if (!f[i][j][k][0] && !f[i][j][k][1]) continue;
                for (int l = j; l <= m; ++l) {
                    int nv = max(l - j - k, 0), nk = k - (l - j - nv);
                    if (nk >= n - i) --nk;
                    ++nk;
                    f[i + 1][l][nk][0] = (f[i + 1][l][nk][0] + f[i][j][k][0]) % P;
                    f[i + 1][l][nk][1] = (f[i + 1][l][nk][1] + f[i][j][k][1]) % P;
                    f[i + 1][l][nk][1] = (f[i + 1][l][nk][1] + 1ll * f[i][j][k][0] * nv) % P;
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i <= m; ++i) if (vis[n][i]) {
        for (int j = 0; j <= n; ++j) {
            ((res += f[n][i][j][1]) >= P) && (res -= P);
        }
    }
    printf("%d\n", res);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5976kb

input:

5
3 1 2 3
1 2
0
4 0 2 3 4
2 2 3

output:

0

result:

ok "0"

Test #2:

score: 0
Accepted
time: 1ms
memory: 8108kb

input:

5
4 1 2 3 7
4 5 7 8 9
4 2 3 6 9
5 0 1 4 7 9
8 0 1 2 3 6 7 8 9

output:

16

result:

ok "16"

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 6492kb

input:

10
8 1 2 3 7 15 17 18 19
11 1 2 5 8 9 10 13 16 18 19 20
12 0 1 4 5 6 7 8 9 11 16 17 19
12 0 1 3 5 9 10 11 15 16 17 18 19
6 2 8 11 15 18 19
11 0 4 6 7 8 10 11 13 16 18 19
13 1 3 4 6 8 9 10 12 13 14 15 19 20
13 2 4 5 8 9 10 11 13 14 15 16 17 20
10 2 3 5 6 8 10 13 14 18 19
12 2 3 4 5 8 9 12 13 15 16 19...

output:

67683

result:

wrong answer 1st words differ - expected: '27895', found: '67683'