結果

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

ソースコード

diff # 

MOD = 10**9 + 7

N = int(input())

result = 0

for a1 in range(1, N + 1):
    dp_prev = [0] * (N + 2)  # 1-based indexing
    dp_prev[a1] = 1
    
    for i in range(2, N + 1):
        # Compute prefix sums for dp_prev
        prefix = [0] * (N + 2)
        for b in range(1, N + 1):
            prefix[b] = (prefix[b - 1] + dp_prev[b]) % MOD
        
        dp_curr = [0] * (N + 2)
        for a in range(1, N + 1):
            # Previous box's index is i-1, so condition is b - (i-1) < a => b < a + (i-1)
            max_b = min(N, a + (i - 1) - 1)
            if max_b < 1:
                continue
            total = (prefix[max_b] - prefix[0]) % MOD  # sum from 1 to max_b
            dp_curr[a] = total
        
        dp_prev = dp_curr
    
    # After processing all boxes, check if aN <= a1
    # Compute prefix sum for the last dp_prev
    prefix_final = [0] * (N + 2)
    for a in range(1, N + 1):
        prefix_final[a] = (prefix_final[a - 1] + dp_prev[a]) % MOD
    cnt = (prefix_final[a1] - prefix_final[0]) % MOD
    result = (result + cnt) % MOD

print(result)
0