Submission #514864

#	Time	Username	Problem	Language	Result	Execution time	Memory
514864		losmi247	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	34 ms	22980 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
const int mod = 1000000007;

ll n,s,e;
ll dp[N][N];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    /*freopen("kangaroo.in","r",stdin);
    freopen("kangaroo.out","w",stdout);*/

    cin >> n >> s >> e;

    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(ll j = 1; j <= i; j++){
            if(i == s){
                /// create a new component at the beginning or just put it at the beginning
                dp[i][j] += dp[i-1][j-1]+dp[i-1][j];
                dp[i][j] %= mod;
                continue;
            }
            if(i == e){
                /// create a new component at the end or just put it at the end
                dp[i][j] += dp[i-1][j-1]+dp[i-1][j];
                dp[i][j] %= mod;
                continue;
            }

            /// create a new component
            dp[i][j] += (dp[i-1][j-1]*(j-(i > s)-(i > e)))%mod;
            dp[i][j] %= mod;
            /// we can't put new elements at the ends or the beginnings of existing components
            /// merge two components - always valid
            dp[i][j] += (dp[i-1][j+1]*j)%mod;
            dp[i][j] %= mod;
        }
    }

    cout << dp[n][1] << endl;
}

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