結果

問題 No.2199 lower_bound and upper_bound
ユーザー lam6er
提出日時 2025-04-09 21:02:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,753 bytes
コンパイル時間 448 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 252,796 KB
最終ジャッジ日時 2025-04-09 21:05:09
合計ジャッジ時間 4,513 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    N, L, U = map(int, sys.stdin.readline().split())
    max_s = U
    offset = N + max_s  # Enough to handle s from -N to U

    # DP array, size such that it can handle s from -N to U
    size = offset * 2 + 2  # Includes from -N - something to U + something, but adjust based on needs
    prev_dp = [0] * (size)
    prev_dp[offset + 0] = 1  # Starting with sum 0 at step 0

    for step in range(1, N+1):
        current_dp = [0] * (size)
        # Cumulative sum array
        cum_sum = [0] * (size)
        cum_sum[0] = prev_dp[0]
        for i in range(1, size):
            cum_sum[i] = (cum_sum[i-1] + prev_dp[i]) % MOD
        
        # The current s can range from -step to U
        min_current = -step
        max_current = U

        for s_current in range(min_current, max_current + 1):
            # s_prev can be from max(-(step-1), s_current +1 -1) ??
            s_prev_min = -(step -1)
            s_prev_max = min(s_current +1, U)

            idx_current = s_current + offset

            # Convert s_prev_min and s_prev_max to indices in prev_dp
            idx_min = s_prev_min + offset
            idx_max = s_prev_max + offset

            if idx_min < 0:
                sum_val = cum_sum[idx_max] if idx_max >=0 else 0
            else:
                sum_val = (cum_sum[idx_max] - cum_sum[idx_min -1]) % MOD
            
            current_dp[idx_current] = sum_val % MOD

        prev_dp = current_dp
    
    # Now sum all s >= L in prev_dp
    res = 0
    start = L
    end = U  # Because sum is <= U due to prefix constraints

    for s in range(start, end +1):
        res = (res + prev_dp[s + offset]) % MOD
    
    print(res % MOD)

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