Submission #1323352

#TimeUsernameProblemLanguageResultExecution timeMemory
1323352hanoonKangaroo (CEOI16_kangaroo)C++20
100 / 100
69 ms31900 KiB
#include <bits/stdc++.h>

#define ll long long
#define int ll
#define ld long double
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define vi vector<int>
#define vvi vector<vi>
#define vvv vector<vvi>
#define vpi vector<pair<int,int>>
#define sz(v) (int)v.size()
#define pb push_back
#define ii pair<int,int>
#define F first
#define S second
using namespace std;
const int mod = 1e9+7, N = 100+5 ,M=1005;
const ll inf = 1e18;
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};

int n,s,e;
vvi dp;
int calc(int i,int c){
    if(i>n) return c==1;
    int &ret=dp[i][c];
    if(~ret) return ret;
    ret=0;
    if(i==s||i==e){
        // new comp
        ret+=calc(i+1,c+1)%mod;
        // extend comp
        if(c)
            ret+=calc(i+1,c)%mod;
        ret%=mod;
    }
    else{
        // new comp
        ret+=(c+1-(i>s)-(i>e))* calc(i+1,c+1)%mod;
        // combine 2
        if(c>=2)
            ret+=(c-1)* calc(i+1,c-1)%mod;
        ret%=mod;
    }
    return ret;
}
void here_we_go_again() {
    cin>>n>>s>>e;
    dp.assign(n+5,vi(n+5,-1));
    cout<<calc(1,0);

}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);


    int tc = 1;
//    cin >> tc;
    for(int i=1;i<=tc;++i) {
//        cout<<"Case #"<<i<<": ";
        here_we_go_again();
    }

    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...