Submission #647641

#	Time	Username	Problem	Language	Result	Execution time	Memory
647641		MON	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	42 ms	15996 KiB

kangaroo

#include<iostream>
using namespace std;

const int NMAX = 2e3 + 1;
const int MOD = 1e9 + 7;

int dp[NMAX][NMAX];

int main()
{
    int n,s,f;
    cin >> n >> s >> f;

    dp[1][1] = 1;
    for(int i = 2; i <= n ; i++)
        {
            for(int j = 1; j < n ; j++)
                {
                    if(i == s || i == f)
                        {
                            dp[i][j] += (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD;
                            dp[i][j] %= MOD;
                        }

                    else
                        {
                            //combinam doua componente

                            dp[i][j] += 1LL * dp[i - 1][j + 1] * j % MOD;
                            dp[i][j] %= MOD;

                            //creeam una noua

                            dp[i][j] += 1LL * dp[i - 1][j - 1] * (j - (i > s) - (i > f)) % 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