結果

問題 No.535 自然数の収納方法
コンテスト
ユーザー vjudge1
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
}
0