Submission #1085625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085625		juicy	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	27 ms	16016 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2005, M = 1e9 + 7;

void add(int &x, int y) {
  if ((x += y) >= M) {
    x -= M;
  }
}

int n, s, f;
int dp[N][N];

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  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) {
        add(dp[i][j], dp[i - 1][j]);
        add(dp[i][j], dp[i - 1][j - 1]);
      } else {
        add(dp[i][j], (long long) dp[i - 1][j + 1] * j % M);
        add(dp[i][j], (long long) dp[i - 1][j - 1] * (j - (i > s) - (i > f)) % M);
      }
    }
  }
  cout << dp[n][1];
  return 0;
}

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