Submission #1036211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036211		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	88 ms	126248 KiB

kangaroo

/*For today, you happen to be the defeated. But what will you become tomorrow?*/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define int long long int 
#define dbg if(debugg)
#define F first 
#define S second 

bool debugg = false;

template <typename T>
using order_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;

template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());  

const int mod = 1000000007;
int n, s, e;
int dp[2002][2002][2][2];
int f(int pos, int comp, int p, int q)
{
    if(comp <= 0) return 0;
    if(pos == 0) return comp == 1;
    int &ans = dp[pos][comp][p][q];
    if(~ans) return ans;
    ans = 0;
    if(pos == s){
        ans += f(pos - 1, comp + 1, 1, q) + f(pos - 1, comp, 1, q);
        ans %= mod;
    }

    else if(pos == e){
        ans += f(pos - 1, comp + 1, p, 1) + f(pos - 1, comp, p, 1);
        ans %= mod;
    }

    else{
        ans += f(pos - 1, comp - 1, p, q) * (comp - 1);
        ans += f(pos - 1, comp + 1, p, q) * (comp + 1 - p - q);
        ans %= mod;
    }
    return ans;
}
void solve()
{
    cin >> n >> s >> e;
    memset(dp, -1, sizeof(dp));
    cout << f(n - 1, 1, n == s, n == e);
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
        
    int t = 1;
    // cin >> t;
    
    while(t--){
        solve();
    }

    return 0;
}

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