結果
問題 | No.2625 Bouns Ai |
ユーザー |
|
提出日時 | 2024-02-11 01:47:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 786 ms / 2,000 ms |
コード長 | 1,463 bytes |
コンパイル時間 | 133 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 261,552 KB |
最終ジャッジ日時 | 2024-09-28 17:23:38 |
合計ジャッジ時間 | 13,699 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
import sys, time, randomfrom collections import deque, Counter, defaultdictinput = lambda: sys.stdin.readline().rstrip()ii = lambda: int(input())mi = lambda: map(int, input().split())li = lambda: list(mi())inf = 2 ** 61 - 1mod = 998244353class Cumsum1d():def __init__(self, A):self.n = len(A)self.Suma = [0] * (self.n + 1)for i in range(self.n):self.Suma[i + 1] += self.Suma[i] + A[i]def query(self, l, r):#0-indexedreturn self.Suma[r] - self.Suma[l]def get(self, i):return self.Suma[i + 1] - self.Suma[i]def __getitem__(self, p):if isinstance(p, int):return self.get(p)else:return self.query(p.start, p.stop)n = ii()a = li()maxi = 10 ** 5dp = [0] * (maxi + 1)for i in range(0, maxi + 1):if i + a[0] > maxi:breakdp[i] = 1for i in range(1, n):e = [0] * (maxi + 1)DP = Cumsum1d(dp)for j in range(0, maxi + 1):#人iが仮スコアj点を取ったとする#この時、si-1 <= si かつ si-1 + ai-1 <= si + ai#=> si-1 + ai-1 - ai <= si が成り立つ必要があるから、#この時人i-1の仮スコアは0以上min(j,j+ai-1-ai)以下でないといけない#累積和持ってDPif j + a[i] > maxi:breake[j] += DP[0:max(0, min(j,j+a[i]-a[i-1]) + 1)]e[j] %= moddp = eprint(sum(dp) % mod)