結果
問題 | No.2625 Bouns Ai |
ユーザー | Mao-beta |
提出日時 | 2024-02-27 03:35:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 671 ms / 2,000 ms |
コード長 | 4,927 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 77,324 KB |
最終ジャッジ日時 | 2024-02-27 03:36:00 |
合計ジャッジ時間 | 14,695 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 59 ms
69,352 KB |
testcase_01 | AC | 53 ms
65,100 KB |
testcase_02 | AC | 86 ms
77,160 KB |
testcase_03 | AC | 517 ms
77,148 KB |
testcase_04 | AC | 489 ms
77,152 KB |
testcase_05 | AC | 556 ms
77,152 KB |
testcase_06 | AC | 490 ms
77,148 KB |
testcase_07 | AC | 550 ms
77,168 KB |
testcase_08 | AC | 571 ms
77,176 KB |
testcase_09 | AC | 568 ms
77,176 KB |
testcase_10 | AC | 565 ms
77,160 KB |
testcase_11 | AC | 61 ms
71,516 KB |
testcase_12 | AC | 575 ms
77,176 KB |
testcase_13 | AC | 662 ms
77,308 KB |
testcase_14 | AC | 661 ms
77,308 KB |
testcase_15 | AC | 571 ms
77,176 KB |
testcase_16 | AC | 671 ms
77,308 KB |
testcase_17 | AC | 631 ms
77,300 KB |
testcase_18 | AC | 611 ms
77,176 KB |
testcase_19 | AC | 604 ms
77,308 KB |
testcase_20 | AC | 560 ms
77,304 KB |
testcase_21 | AC | 556 ms
77,176 KB |
testcase_22 | AC | 620 ms
77,324 KB |
testcase_23 | AC | 632 ms
77,308 KB |
testcase_24 | AC | 545 ms
77,308 KB |
testcase_25 | AC | 606 ms
77,320 KB |
ソースコード
import sys import math import bisect from heapq import heapify, heappop, heappush from collections import deque, defaultdict, Counter from functools import lru_cache from itertools import accumulate, combinations, permutations, product sys.setrecursionlimit(1000000) MOD = 10 ** 9 + 7 MOD99 = 998244353 input = lambda: sys.stdin.readline().strip() NI = lambda: int(input()) NMI = lambda: map(int, input().split()) NLI = lambda: list(NMI()) SI = lambda: input() SMI = lambda: input().split() SLI = lambda: list(SMI()) EI = lambda m: [NLI() for _ in range(m)] class segtree(): n = 1 size = 1 log = 2 d = [0] op = None e = 10 ** 15 def __init__(self, V, OP, E): self.n = len(V) self.op = OP self.e = E self.log = (self.n - 1).bit_length() self.size = 1 << self.log self.d = [E for i in range(2 * self.size)] for i in range(self.n): self.d[self.size + i] = V[i] for i in range(self.size - 1, 0, -1): self.update(i) def set(self, p, x): assert 0 <= p and p < self.n p += self.size self.d[p] = x for i in range(1, self.log + 1): self.update(p >> i) def get(self, p): assert 0 <= p and p < self.n return self.d[p + self.size] def prod(self, l, r): assert 0 <= l and l <= r and r <= self.n sml = self.e smr = self.e l += self.size r += self.size while (l < r): if (l & 1): sml = self.op(sml, self.d[l]) l += 1 if (r & 1): smr = self.op(self.d[r - 1], smr) r -= 1 l >>= 1 r >>= 1 return self.op(sml, smr) def all_prod(self): return self.d[1] def max_right(self, l, f): """ 0≤l<Nなる整数 l および条件式 f が与えられたとき、 f(prod(l,r))=True となる最大の r を求める。 ただし、与えられる条件式 f は次を満たす: ある整数 x>l に対し、f(prod(l,x))=True であるとき、 任意の整数 l<y≤x について f(prod(l,y))=True である。また、f(e)=True である。 ->lから右にprodを伸ばしていくとき、はじめて条件がFalseになるrをさがす """ assert 0 <= l and l <= self.n assert f(self.e) if l == self.n: return self.n l += self.size sm = self.e while (1): while (l % 2 == 0): l >>= 1 if not (f(self.op(sm, self.d[l]))): while (l < self.size): l = 2 * l if f(self.op(sm, self.d[l])): sm = self.op(sm, self.d[l]) l += 1 return l - self.size sm = self.op(sm, self.d[l]) l += 1 if (l & -l) == l: break return self.n def min_left(self, r, f): """ 0≤r<Nなる整数 r および条件式 f が与えられたとき、 f(prod(l,r))=True となる最小の l を求める。 ただし、与えられる条件式 f は次を満たす: ある整数 x<r に対し、f(prod(x,r))=True であるとき、 任意の整数 x≤y<r について f(prod(y,r))=True である。また、f(e)=True である。 ->rから左にprodを伸ばしていくとき、はじめて条件がFalseになるlをさがす """ assert 0 <= r and r < self.n assert f(self.e) if r == 0: return 0 r += self.size sm = self.e while (1): r -= 1 while (r > 1 & (r % 2)): r >>= 1 if not (f(self.op(self.d[r], sm))): while (r < self.size): r = (2 * r + 1) if f(self.op(self.d[r], sm)): sm = self.op(self.d[r], sm) r -= 1 return r + 1 - self.size sm = self.op(self.d[r], sm) if (r & -r) == r: break return 0 def update(self, k): self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1]) def __str__(self): return str([self.get(i) for i in range(self.n)]) def main(): N = NI() A = NLI() M = 100000 dp = [0] * (M+1) dp2 = [0] * (M+1) for i in range(1, N+1): cum = 0 for j in range(M+1): if i == 1: if j >= A[0]: dp2[j] = 1 else: idx = min(j, j+A[i-2]-A[i-1]) if 0 <= idx <= M: cum += dp[idx] cum %= MOD99 dp2[j] = cum dp, dp2 = dp2, dp print(sum(dp) % MOD99) if __name__ == "__main__": main()