Submission #872888

#	Time	Username	Problem	Language	Result	Execution time	Memory
872888		San7y	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	1 ms	364 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

#define forn(i, n) for(int i = 0; i < n; i++)
#define MOD(x) (((x) % mod + mod) % mod)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<int> vi;
typedef vector<pii> vp;

const ll LN = 0, LM = 0, mod = 1e9 + 7;

ll dp[2002][2002];
/*
dp[i][j]
- first i elements inserted (indexed at 0)
- with j components
*/

void solve() {
    ll N, cs, cf;
    cin >> N >> cs >> cf;
    if (N == 2) { // special case
        cout << 1;
        return;
    }
    dp[1][1] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 1; j <= i; j++) {
            // The element i + 1 creates its own cc
            dp[i + 1][j + 1] = MOD(dp[i + 1][j + 1] + dp[i][j]);
            
            // The endpoints joins to an existing component.
            if (i + 1 == cs || i + 1 == cf) {
                if (i + 1 == min(cs, cf)) dp[i + 1][j] = MOD(dp[i + 1][j] + MOD(dp[i][j] * j));
                else if (i + 1 == N && j == 1) dp[i + 1][j] = MOD(dp[i + 1][j] + dp[i][j]);
                else if (j >= 2) dp[i + 1][j] = MOD(dp[i + 1][j] + MOD(dp[i][j] * (j - 1)) );
                continue;
            }
            // Joins two cc
            if (j >= 2) {
                if (i + 1 < min(cs, cf)) dp[i + 1][j - 1] = MOD(dp[i + 1][j - 1] + MOD(dp[i][j] * (j) * (j-1)));
                else if (i + 1 < max(cs, cf)) dp[i + 1][j - 1] = MOD(dp[i + 1][j - 1] + MOD(dp[i][j] * ((j-1) * (j-2) + (j-2))));
                else dp[i + 1][j - 1] = MOD(dp[i + 1][j - 1] + MOD(dp[i][j] * ((j-2) * (j-3) + 2 * (j-2) + 1)));
            }
        }
    }

    //for (int i = 1; i <= N; i++)
     //   for (int j = 1; j <= i; j++)
       //     cout << "DP(" << i << ", " << j << "):" << dp[i][j] << endl;

    cout << dp[N][1];
}

int main() {
    #ifdef DEBUG
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int Tc = 1;
    forn(i, Tc) solve();
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49