結果

問題 No.535 自然数の収納方法
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:00:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 767 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 76,696 KB
最終ジャッジ日時 2025-04-09 21:01:21
合計ジャッジ時間 4,276 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 10**9 + 7

N = int(input())
if N == 1:
    print(1)
    exit()

total = 0

for x in range(1, N+1):
    dp = [[0]*(N+2) for _ in range(N+1)]
    dp[1][x] = 1
    for i in range(2, N+1):
        # Precompute cumulative sum
        cum = [0]*(N+2)
        for y in range(1, N+1):
            cum[y] = (cum[y-1] + dp[i-1][y]) % MOD
        # Update dp[i][y]
        for y in range(1, N+1):
            prev_max = min(N, y + (i-1 -1))  # since x_prev < y + (i-1)
            if prev_max >= 1:
                dp[i][y] = cum[prev_max]
            else:
                dp[i][y] = 0
    # After processing all steps, check y <= x
    sum_y = 0
    for y in range(1, x + 1):
        sum_y = (sum_y + dp[N][y]) % MOD
    total = (total + sum_y) % MOD

print(total % MOD)
0