結果

問題 No.2378 Cards and Subsequences
コンテスト
ユーザー LyricalMaestro
提出日時 2025-05-04 00:57:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 579 ms / 2,000 ms
コード長 1,067 bytes
コンパイル時間 934 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 108,808 KB
最終ジャッジ日時 2025-05-04 00:58:10
合計ジャッジ時間 16,207 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2378

MOD = 998244353

def main():
    N, M, K = map(int, input().split())
    S = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    cum_array = [[0] * (N + 1) for _ in range(K + 1)]
    dp = [0] * (K + 1)
    dp[0] = 1

    cum_array[0][0] = 1
    last_s = [-1] * M
    for i in range(N):
        new_dp = [0] * (K + 1)
        s = S[i] - 1
        a = A[s]
        b = B[s]

        for k in range(K + 1):
            for x in (a, b):
                if k - x >= 0:
                    if last_s[s] == -1:
                        new_dp[k] += cum_array[k - x][i]
                    else:
                        new_dp[k] += (cum_array[k - x][i] - cum_array[k - x][last_s[s] - 1]) % MOD
                    new_dp[k] %= MOD
        
        dp = new_dp
        for k in range(K + 1):
            cum_array[k][i + 1] = (dp[k] + cum_array[k][i]) % MOD
        last_s[s] = i + 1
    
    print(cum_array[K][-1])















if __name__ == '__main__':
    main()
0