Submission #442345

#	Time	Username	Problem	Language	Result	Execution time	Memory
442345		Bench0310	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	38 ms	336 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,x,y;
    cin >> n >> x >> y;
    vector<ll> dp(n+1,0);
    dp[0]=1;
    const ll mod=1000000007;
    auto add=[&](ll a,ll b)->ll{return (a+b)%mod;};
    auto mul=[&](ll a,ll b)->ll{return (a*b)%mod;};
    for(int i=1;i<=n;i++)
    {
        vector<ll> ndp(n+1,0);
        for(int j=0;j<=n;j++)
        {
            if(i!=x&&i!=y)
            {
                //merge groups
                if(j>0) ndp[j-1]=add(ndp[j-1],mul(j-1,dp[j]));
                //make new group
                if(j<n&&j+1-(i>x)-(i>y)>=0) ndp[j+1]=add(ndp[j+1],mul(j+1-(i>x)-(i>y),dp[j]));
            }
            else if(i==x)
            {
                //add to front of first group
                ndp[j]=add(ndp[j],dp[j]);
                //make new first group
                if(j<n) ndp[j+1]=add(ndp[j+1],dp[j]);
            }
            else if(i==y)
            {
                //add to end of last group
                ndp[j]=add(ndp[j],dp[j]);
                //make new last group
                if(j<n) ndp[j+1]=add(ndp[j+1],dp[j]);
            }
        }
        dp=ndp;
    }
    cout << dp[1] << "\n";
    return 0;
}

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