結果
問題 | No.2783 4-33 Easy |
ユーザー |
|
提出日時 | 2024-06-14 22:24:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,676 bytes |
コンパイル時間 | 2,675 ms |
コンパイル使用メモリ | 211,396 KB |
最終ジャッジ日時 | 2025-02-21 22:10:31 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <atcoder/modint> #include <bits/stdc++.h> using namespace std; using ll = long long; using mint = atcoder::modint998244353; #define rep(i, n) for (int i = 0; i < (int)(n); i++) void solve() { ll n; cin >> n; vector<pair<ll, ll>> c, d; { vector<ll> a(n); rep(i, n) cin >> a[i]; vector<string> b(n); rep(i, n) cin >> b[i]; rep(i, n) { bool x = false; ll v = 0; rep(j, b[i].size()) { if (b[i][j] == 'X') { x = true; } else { v *= 10; v += b[i][j] - '0'; } } if (x) { d.emplace_back(a[i], v); } else { c.emplace_back(a[i], v); } } } vector dp(10, vector(5, vector<mint>(34, 0))); dp[0][0][0] = 1; for (const auto &[a, b] : c) { vector pre = dp; rep(j, 5) { ll nj = j + a; if (nj >= 5) continue; rep(k, 34) { ll nk = k + b; if (nk >= 34) continue; rep(i, 8) { ll ni = i + 1; dp[ni][nj][nk] += pre[i][j][k]; } } } } for (const auto &[a, b] : d) { rep(j, 5) { ll nj = j + a; if (nj != 4) continue; rep(k, 34) { ll nk = k + b; if (nk != 33) continue; bool ok = true; if (b == 0) { ok &= k == 33; } else { ok &= nj >= nk - 4; } if (ok) dp[9][4][33] += dp[8][4 - a][33 - b]; } } } cout << dp[9][4][33].val() << '\n'; } int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); int T = 1; for (int t = 0; t < T; t++) { solve(); } return 0; }