Submission #873288

#	Time	Username	Problem	Language	Result	Execution time	Memory
873288		_Mahmoud_Ayman	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	44 ms	31912 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll add(ll a,ll b,ll mod)
{
    return ((a%mod)+(b%mod))%mod;
}
ll mul(ll a,ll b,ll mod)
{
    return ((a%mod)*(b%mod))%mod;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,s,e;cin>>n>>s>>e;
    ll dp[n+5][n+5]={};
    dp[1][1]=1;
    for(ll i=2;i<=n;i++)
    {
        for(ll o=1;o<=i;o++)
        {
            if(i==s||i==e)
            {
                dp[i][o]=add(dp[i][o],dp[i-1][o],1000000007); // add to the first or last component
                dp[i][o]=add(dp[i][o],dp[i-1][o-1],1000000007); // create new component at the beginning or the end
            }
            else
            {
                dp[i][o+1]=add(dp[i][o+1],mul(dp[i-1][o],o+1-(i>s)-(i>e),1000000007),1000000007); // create new comp
                if(o) dp[i][o-1]=add(dp[i][o-1],dp[i-1][o]*(o-1),1000000007); // merge two components
            }
        }
    }
    cout<<dp[n][1];
    return 0;
}

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