Submission #105363

#	Time	Username	Problem	Language	Result	Execution time	Memory
105363		the_art_of_war	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	147 ms	64764 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e15;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 1e5 + 100;
const int LOG = 20;
const int mod = 1e9 + 7;
const int MX = 1e6 + 100;
typedef long long li;
const li MOD = 1000000000949747713ll;

int N, S, E;

ll dp[2010][1020][2][2];

ll get(int i, int comp, int le, int ri) {
    if (comp < 0)
        return 0;
    if (2 * comp + 1 > N)
        return 0;
    if (dp[i][comp][le][ri] != -1)
        return dp[i][comp][le][ri];
    ll &res = dp[i][comp][le][ri];
    res = 0;

    if (i == N - 1) {
        if (comp == 0) {
            res = 1;
            //check
        }
        return res;
    }

    if (i == S) {
        //just
        res += get(i + 1, comp, 1, ri);
        //conn
        res += get(i + 1, comp - 1, 1, ri) * comp;

    } else if (i == E) {
        res += get(i + 1, comp, le, 1);
        res += get(i + 1, comp - 1, le, 1) * comp;
    } else {
        //just create
        res += get(i + 1, comp + 1, le, ri);
        //connect
        res += get(i + 1, comp - 1, le, ri) * (1ll * comp * (comp - 1)) % mod;

        if (le > 0) {
            //connect
            res += get(i + 1, comp - 1, le, ri) * comp;
        }
        if (ri > 0) {
            //connect
            res += get(i + 1, comp - 1, le, ri) * comp;
        }
    }
    res%=mod;
    return res;
}

void solve() {
    memset(dp,-1,sizeof dp);
    cin >> N >> S >> E;
    S--; E--;

    cout << get(0,0,0,0)<<"\n";

}

signed main() {
#ifdef zxc
    debug = 1;
    freopen("../input.txt", "r", stdin);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;

    while (t--)
        solve();
    dout << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

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