結果
問題 | No.2625 Bouns Ai |
ユーザー |
![]() |
提出日時 | 2024-02-09 22:29:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 702 ms / 2,000 ms |
コード長 | 764 bytes |
コンパイル時間 | 169 ms |
コンパイル使用メモリ | 82,608 KB |
実行使用メモリ | 226,844 KB |
最終ジャッジ日時 | 2024-09-28 15:43:08 |
合計ジャッジ時間 | 14,581 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
def Map(): return list(map(int,input().split())) mod = 998244353 N = int(input()) A = Map() S = 10**5 if N == 1: print(S + 1 - A[0]) exit() dp = [[0 for j in range(S + 2)] for i in range(N)] for s in range(S + 1): if s + A[0] > S: break dp[0][s] += 1 for n in range(N-1): d = 0 sss = S - A[n+1] + 1 if A[n] - A[n+1] > 0: d += A[n] - A[n+1] for s in range(S+1): if n > 0 and s < S: dp[n][s+1] += dp[n][s] dp[n][s+1] %= mod for s in range(S+1): if s + d >= sss: break ss = s + d dp[n+1][ss] += dp[n][s] dp[n+1][ss] %= mod dp[n+1][sss] -= dp[n][s] dp[n+1][sss] %= mod ans = 0 for s in range(S+1): dp[N-1][s+1] += dp[N-1][s] dp[N-1][s+1] %= mod ans += dp[N-1][s] ans %= mod print(ans)