Submission #873424

#	Time	Username	Problem	Language	Result	Execution time	Memory
873424		JorgeSC	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	32 ms	32348 KiB

kangaroo

// clang-format off
#include <bits/stdc++.h>
using namespace std;

// --------------------------- Defines -------------------------------------  //
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) { 
    return os << '(' << p.first << ", " << p.second << ')'; 
}

template <typename Tc,
          typename T = typename enable_if<!is_same<Tc, string>::value,
                                          typename Tc::value_type>::type>
ostream &operator<<(ostream &os, const Tc &v) {
    os << '{';
    for (const T &x : v) os << x << ',';
    return os << '}';
}

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef DEBUG
    #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
    #define dbg(...)
#endif

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vp;
// --------------------------- Constants ----------------------------------- //
const ll LN = 2e3 + 9, 
         LM = 0, 
         mod = (ll)(1e9) + 7;
// ------------------------- Your code ---------------------------------- //
// clang-format on

void Solve() {
    ll N, cs, cf;
    vector<vl> DP(LN, vl(LN, 0));

    cin >> N >> cs >> cf;

    DP[0][0] = 1;

    for (ll i = 1; i <= N; i++) {
        for (ll j = 1; j <= i; j++) {
            if (i == cs) {
                DP[i][j] = MOD(DP[i - 1][j] + DP[i - 1][j - 1]);
            } else if (i == cf) {
                DP[i][j] = MOD(DP[i - 1][j] + DP[i - 1][j - 1]);
            } else {
                DP[i][j] = MOD(j * DP[i - 1][j + 1]);
                DP[i][j] = MOD(DP[i][j] + MOD((j - 2) * DP[i - 1][j - 1]));
                if (i < cs) DP[i][j] = MOD(DP[i][j] + DP[i - 1][j - 1]);
                if (i < cf) DP[i][j] = MOD(DP[i][j] + DP[i - 1][j - 1]);
            }
        }
    }

    cout << DP[N][1] << '\n';
}

// clang-format off
// --------------------------------------------------------------------- //
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