QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133733#4934. Forbidden CardSolitaryDream#WA 1ms22016kbC++202.2kb2023-08-02 13:37:392023-08-02 13:37:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 13:37:42]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:22016kb
  • [2023-08-02 13:37:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int p = 998244353;
const int N = 105;
int C[N][N];
int n, m, f[N][N][2][2][N], sm[N];
vector<pii> ball;
inline int DP(int l, int r, int cl, int cr, int k) {
    if (l + 1 == r) return k == 0;
    int &curf = f[l][r][cl][cr][k];
    if (curf != -1) return curf;
    curf = 0;
    for (int i = l + 1; i < r; ++i) if (ball[i].second != 2) {
        for (int j = 0; j <= k; ++j) curf = (curf + 1ll * DP(l, i, cl, ball[i].second, j) * DP(i, r, ball[i].second, cr, k - j)) % p;
        curf = 1ll * curf * C[sm[r] - sm[l]][sm[i] - sm[l]] % p;
    }
    for (int i = l + 1; i < r; ++i) {
        int val = 0;
        int x = ball[l].first, y = ball[i].first, z = ball[r].first;
        int cur_col = (y - x <= z - y ? ball[l].second : ball[r].second);
        int nk = k - (cur_col == 1);
        for (int j = 0; j <= nk; ++j) val = (val + 1ll * DP(l, i, cl, cur_col, j) * DP(i, r, cur_col, cr, nk - j)) % p;
        curf = (curf + 1ll * val * C[sm[r - 1] - sm[l] - 1][sm[i - 1] - sm[l]] ) % p;
    }
    return curf;
}
int main() {
    for (int i = 0; i < N; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
    }
    scanf("%d%d", &n, &m);
    memset(f, -1, sizeof f);
    int red_minus_black = 0;
    for (int i = 1; i <= n; ++i) {
        int ps;
        char col[10];
        scanf("%d%s", &ps, col);
        ball.push_back(pii(ps, *col == 'R'));
        red_minus_black += (*col == 'R' ? 1 : -1);
    }
    int col_left = min_element(ball.begin(), ball.end())->second;
    int col_right = min_element(ball.begin(), ball.end())->second;
    ball.push_back(pii(-1, col_left));
    ball.push_back(pii(1.1e9, col_right));
    for (int i = 1; i <= m; ++i) {
        int ps;
        scanf("%d", &ps);
        ball.push_back(pii(ps, 2));
    }
    sort(ball.begin(), ball.end());
    for (int i = 1; i < (int)ball.size(); ++i) sm[i] = sm[i - 1] + (ball[i].second == 2);
    long long ans = 0;
    for (int i = 0; i <= m; ++i) if (i - (m - i) + red_minus_black > 0) {
        ans += DP(0, ball.size() - 1, ball.front().second, ball.back().second, i);
    }
    printf("%lld\n", ans % p);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 22016kb

input:

3 6
1 2
2 4
4 2

output:

0

result:

wrong answer 1st lines differ - expected: '3', found: '0'