結果
問題 |
No.535 自然数の収納方法
|
ユーザー |
![]() |
提出日時 | 2025-03-17 19:29:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 1,029 bytes |
コンパイル時間 | 1,623 ms |
コンパイル使用メモリ | 162,744 KB |
実行使用メモリ | 66,084 KB |
最終ジャッジ日時 | 2025-03-17 19:29:54 |
合計ジャッジ時間 | 3,264 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> #define int long long using namespace std; const int MOD = 1000000007; int dp[2001][2001]; int DP[2001][2001]; int a[2001]; signed main() { int n; cin >> n; dp[0][0] = 1; if(n >= 1) { DP[1][1] = 1; } for(int i = 2; i < n; i++) { a[i] = i - 2; } for(int i = 1; i <= n; i++) { static int s[2001]; static int t[2001]; for(int j = 0; j <= n; j++) { s[j] = dp[i - 1][j]; t[j] = DP[i - 1][j]; } for(int j = 1; j <= n; j++) { s[j] = (s[j] + s[j - 1]) % MOD; t[j] = (t[j] + t[j - 1]) % MOD; } for(int j = 1; j <= n; j++) { int idx = min(n, j + a[i - 1]); dp[i][j] = s[idx]; if(i != 1) { DP[i][j] = t[idx]; } } } int sum = 0; for(int i = 1; i <= n; i++) { sum = (sum + dp[n][i]) % MOD; } cout << (sum - DP[n][n] + MOD) % MOD << endl; return 0; }