Submission #873240

#	Time	Username	Problem	Language	Result	Execution time	Memory
873240		San7y	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	29 ms	23220 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 1)
- with j components
*/

void solve() {
    ll N, cs, cf;
    cin >> N >> cs >> cf;
    if (N == 2) { // special case
        cout << 1;
        return;
    }

//    forn(i, N + 1) forn(j, N + 1) dp[i][j] = 0;
    dp[1][1] = 1;
    for (ll i = 1; i < N; i++) {
        for (ll j = 1; j <= i; j++) {
            if (!dp[i][j]) continue;

            // The endpoints
            if (i + 1 == cs || i + 1 == cf) {
                // Creates its own component
                dp[i + 1][j + 1] = MOD(dp[i + 1][j + 1] + dp[i][j]);
                // Joins the left / right most component.
                dp[i + 1][j] = MOD(dp[i + 1][j] + dp[i][j]);
            } else {
                // Creates its own component
                dp[i + 1][j + 1] = MOD(dp[i + 1][j + 1] + MOD(dp[i][j] * (j + 1 - (i + 1 > cs) - (i + 1 > cf))));
                // Joins two existing component
                if (j >= 2) dp[i + 1][j - 1] = MOD(dp[i + 1][j - 1] + MOD(dp[i][j] * (j-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] << '\n';
}

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; //cin >> Tc;
    forn(i, Tc) solve();
    return 0;
}

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