結果
問題 | No.2378 Cards and Subsequences |
ユーザー |
|
提出日時 | 2023-07-07 23:15:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 810 ms / 2,000 ms |
コード長 | 1,428 bytes |
コンパイル時間 | 3,880 ms |
コンパイル使用メモリ | 258,620 KB |
最終ジャッジ日時 | 2025-02-15 08:28:11 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 35 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;using ll = long long;using vll = vector<ll>;using vvll = vector<vll>;using mint = modint998244353;using vm = vector<mint>;using vvm = vector<vm>;using vb = vector<bool>;using vvb = vector<vb>;using vvvb = vector<vvb>;using vd = vector<double>;using vvd = vector<vd>;using vvvd = vector<vvd>;#define rep(i,n) for(ll i=(ll)(0); i<(ll(n)); ++i)#define all(x) (x).begin(), (x).end()mint op(mint a, mint b) {return a + b;};mint e() { return 0; };int main() {ll N, M, K;cin >> N >> M >> K;vll S(N);vll A(M), B(M);rep(i, N) {cin >> S[i];S[i]--;}rep(i, M)cin >> A[i];rep(i, M)cin >> B[i];vector<segtree<mint, op, e>> seg(K + 1);rep(i, K + 1) {segtree<mint, op, e> SE(N + 1);seg[i] = SE;}seg[0].set(0, 1);vll L(M, 0);rep(i, N) {ll s = S[i];rep(k, K + 1) {mint d = seg[k].prod(L[s], i + 1);if (k + A[s] <= K) {mint e = seg[k + A[s]].get(i + 1);seg[k + A[s]].set(i + 1, d+e);}if (k + B[s] <= K) {mint e = seg[k + B[s]].get(i + 1);seg[k + B[s]].set(i + 1, d + e);}}L[s] = i+1;}mint an = seg[K].all_prod();cout << an.val() << endl;}