Submission #1287935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287935		behrad	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	58 ms	55184 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 2005, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, S, T;
ll dp[maxn][maxn][3];

constexpr inline void md(ll& a) {
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> S >> T;
  
	dp[1][1][(S == 1 || T == 1)] = 1;
  
  for (int i = 2 ; i <= n ; i ++) {
    for (int j = 1 ; j < i ; j ++) {
			if (i == S || i  == T) {
				for (int k : {0, 1}) {
					md(dp[i][j + 1][k + 1] += dp[i - 1][j][k]);
					md(dp[i][j][k + 1] += dp[i - 1][j][k]);
				}
			} else {
				for (int k : {0, 1, 2}) {
					dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i - 1][j][k] * (j + 1 - k)) % mod;
					dp[i][j - 1][k] = (dp[i][j - 1][k] + dp[i - 1][j][k] * (j - 1)) % mod;
				}
			}   
    }
  }
  cout << dp[n][1][2] % mod << endl;
}

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