Submission #1086914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086914		Gabituss	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	36 ms	31836 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

//@formatter:off
using ll = long long;
template<typename T> istream &operator>>(istream &is, vector<T> &a);
template<typename T> ostream &operator<<(ostream &os, vector<T> &a);
//@formatter:on
#define int long long
const int mod = 1e9 + 7;

signed main() {
#ifdef LOCAL
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
#else
      ios_base::sync_with_stdio(false);
      cin.tie(0);
#endif

      int n, a, b;
      cin >> n >> a >> b;

      a--, b--;

      vector<vector<int>> dp(n + 1, vector<int>(n + 1));
      dp[0][0] = 1;

      for (int i = 0; i < n; ++i) {
            for (int comp = 0; comp < n; ++comp) {
                  if (i == a || i == b) {
                        dp[i + 1][comp + 1] += dp[i][comp];
                        dp[i + 1][comp] += dp[i][comp];
                        dp[i + 1][comp + 1] %= mod;
                        dp[i + 1][comp] %= mod;
                  } else {
                        dp[i + 1][comp + 1] += dp[i][comp] * (comp + 1 - (a <= i) - (b <= i));
                        if (comp > 0)dp[i + 1][comp - 1] += dp[i][comp] * (comp - 1);
                        dp[i + 1][comp + 1] %= mod;
                        dp[i + 1][comp - 1] %= mod;
                  }
            }
      }

      cout << dp[n][1] << "\n";
}

// region POZOR
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
      for (int i = 0; i < a.size(); i++)
            os << a[i] << " \n"[i == a.size() - 1];
      return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
      for (auto &i: a)
            is >> i;
      return is;
}
// endregion

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