Submission #789266

#	Time	Username	Problem	Language	Result	Execution time	Memory
789266		cig32	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	21 ms	31948 KiB

kangaroo

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2023;
const int MOD = 1e9 + 7;
int dp[MAXN][MAXN], n, a, b;
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> a >> b;
  if(a > b) swap(a, b);
  dp[1][1] = 1;
  for(int i=2; i<=n; i++) {
    for(int j=1; j<=n; j++) {
      if(i == a || i == b) {
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
      }
      else if(i < a) {
        dp[i][j] = (j * dp[i-1][j-1] + j * dp[i-1][j+1]) % MOD;
      }
      else if(a < i && i < b) {
        dp[i][j] = ((j-1) * dp[i-1][j-1] + j * dp[i-1][j+1]) % MOD;
      }
      else {
        dp[i][j] = (max(0ll, j-2) * dp[i-1][j-1] + j * dp[i-1][j+1]) % MOD;
      }
    }
  }
  cout << dp[n][1] << "\n";
}

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