제출 #1365050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365050		vjudge1	캥거루 (CEOI16_kangaroo)	C++20	100 / 100	25 ms	31808 KiB

kangaroo

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int mod = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, cs, cf;
        cin >> n >> cs >> cf;

        vector<vector<int>> dp(n + 1, vector<int>(n + 1)); // index - cc
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                        if (i == cs || i == cf) {
                                // stick
                                dp[i][j] += dp[i - 1][j];
                                dp[i][j] %= mod;

                                // new
                                dp[i][j] += dp[i - 1][j - 1];
                                dp[i][j] %= mod;
                        } else {
                                // new
                                dp[i][j] += dp[i - 1][j - 1] * (j - (i >= cs) - (i >= cf)); // aslinya j tempat, tp kalo ujung dh ada, brrt gabisa lg
                                dp[i][j] %= mod;

                                // gada stick soalnya ga bisa menjamin zigzag

                                // merge
                                if (j + 1 <= n) {
                                        dp[i][j] += dp[i - 1][j + 1] * j % mod;  // gabung di sela"nya, ada j cara
                                        dp[i][j] %= mod;
                                }
                        }
                }
        }

        cout << dp[n][1] << '\n';
        
        return 0;
}

• 서브태스크 1: 6 / 6
• 서브태스크 2: 30 / 30
• 서브태스크 3: 15 / 15
• 서브태스크 4: 49 / 49