結果
問題 | No.2378 Cards and Subsequences |
ユーザー |
|
提出日時 | 2023-07-13 14:25:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 1,657 bytes |
コンパイル時間 | 3,367 ms |
コンパイル使用メモリ | 185,284 KB |
最終ジャッジ日時 | 2025-02-15 10:12:49 |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 35 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <functional>#include <cmath>#include <iomanip>#include <stack>#include <queue>#include <numeric>#include <map>#include <unordered_map>#include <set>#include <fstream>#include <chrono>#include <random>#include <bitset>#include <atcoder/all>#define rep(i,n) for(int i=0;i<(n);i++)#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) ((int)(x).size())#define pb push_backusing ll = long long;using namespace std;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}const ll mod = 998244353;int main(){ll N,M,K; cin >> N >> M >> K;vector<ll> S(N);rep(i,N) cin >> S[i];rep(i,N) S[i]--;vector<ll> A(M),B(M);rep(i,M) cin >> A[i];rep(i,M) cin >> B[i];vector<vector<ll>> dp(N+1,vector<ll>(K+1,0));vector<vector<ll>> dps(N+2,vector<ll>(K+1,0));dps[1][0] = 1;dp[0][0] = 1;for(int i=1;i<=N;i++){int s = S[i-1];vector<ll> V = dps[i];int p = i-1;while(p-1 >= 0){if(S[p-1]!=s) p--;else break;}rep(j,K+1) V[j] = ( V[j] - dps[p][j] + mod ) % mod;rep(j,K+1){if(j-A[s] >= 0) dp[i][j] += V[j-A[s]];if(j-B[s] >= 0) dp[i][j] += V[j-B[s]];dp[i][j] %= mod;}rep(j,K+1){dps[i+1][j] = (dps[i][j] + dp[i][j]) % mod;}}ll ans = 0;rep(i,N+1) ans += dp[i][K];cout << ans % mod << '\n';return 0;};