Submission #869351

#	Time	Username	Problem	Language	Result	Execution time	Memory
869351		bruh	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	47 ms	71012 KiB

kangaroo

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 2002, mod = 1e9 + 7;
int dp[maxn][maxn][2][2];
int n, s, e;

inline void add(int &a, int b)
{
    a += b;
    if (a >= mod) a %= mod;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> s >> e;
    dp[1][1][(s == 1)][(e == 1)] = 1;
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j <= i; j++)
            for (int l = 0; l < 2; l++) for (int r = 0; r < 2; r++)
                if (dp[i][j][l][r])
                {
                    int l2 = (i + 1 == s), r2 = (i + 1 == e);
                    if (!l2 && !r2)
                    {
                        add(dp[i + 1][j + 1][l2 | l][r2 | r], dp[i][j][l][r] * (j + 1 - l - r));
                        add(dp[i + 1][j - 1][l][r], dp[i][j][l][r] * (j - 1));
                    }
                    else add(dp[i + 1][j + 1][l2 | l][r2 | r], dp[i][j][l][r]);
                    if (l2)
                        add(dp[i + 1][j][1][r], dp[i][j][l][r]);
                    if (r2)
                        add(dp[i + 1][j][l][1], dp[i][j][l][r]);
                }
    }
    cout << dp[n][1][1][1];
}

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