QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133733 | #4934. Forbidden Card | SolitaryDream# | WA | 1ms | 22016kb | C++20 | 2.2kb | 2023-08-02 13:37:39 | 2023-08-02 13:37:42 |
Judging History
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'