結果
問題 |
No.535 自然数の収納方法
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)