Submission #858901

#	Time	Username	Problem	Language	Result	Execution time	Memory
858901		Tenis0206	Kangaroo (CEOI16_kangaroo)	C++11	100 / 100	24 ms	23132 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

const int nmax = 2000;
const int Mod = 1e9 + 7;

int n,cs,cf;

long long dp[nmax + 5][nmax + 5];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>cs>>cf;
    if(cs > cf)
    {
        swap(cs,cf);
    }
    dp[0][0] = 1;
    for(int i=0; i<n; i++)
    {
        for(int nrg=0; nrg<=i; nrg++)
        {
            int val = i + 1;

            /// creez grup nou
            if(val == cs)
            {
                dp[i + 1][nrg + 1] += dp[i][nrg];
                dp[i + 1][nrg + 1] %= Mod;
            }
            else if(val == cf)
            {
                dp[i + 1][nrg + 1] += dp[i][nrg];
                dp[i + 1][nrg + 1] %= Mod;
            }
            else
            {
                if(val < cs)
                {
                    dp[i + 1][nrg + 1] += 1LL * dp[i][nrg] * (nrg + 1) % Mod;
                    dp[i + 1][nrg + 1] %= Mod;
                }
                else if(val < cf)
                {
                    dp[i + 1][nrg + 1] += 1LL * dp[i][nrg] * nrg % Mod;
                    dp[i + 1][nrg + 1] %= Mod;
                }
                else if(nrg > 1)
                {
                    dp[i + 1][nrg + 1] += 1LL * dp[i][nrg] * (nrg - 1) % Mod;
                    dp[i + 1][nrg + 1] %= Mod;
                }
            }

            /// unesc doua grupuri existente
            if(val != cs && val != cf && nrg > 1)
            {
                dp[i + 1][nrg - 1] += 1LL * dp[i][nrg] * (nrg - 1) % Mod;
                dp[i + 1][nrg - 1] %= Mod;
            }

            /// adaug la inceput
            if(val == cs)
            {
                dp[i + 1][nrg] += dp[i][nrg];
                dp[i + 1][nrg] %= Mod;
            }

            /// adaug la final
            if(val == cf)
            {
                dp[i + 1][nrg] += dp[i][nrg];
                dp[i + 1][nrg] %= Mod;
            }
        }
    }
     cout<<dp[n][1]<<'\n';
    return 0;
}

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