Submission #1298316

#TimeUsernameProblemLanguageResultExecution timeMemory
1298316vuqar_bazarov1Kangaroo (CEOI16_kangaroo)C++20
36 / 100
424 ms589824 KiB
#pragma GCC optimize("Ofast,unroll-loops,O3")
#include <bits/stdc++.h>

using namespace std;

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

using int64 = int64_t;
using ld = long double;
using uint64 = uint64_t;
using int128 = __int128_t;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

const int md = 1e9 + 7;
const int64 inf = 1e18;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, cs, cf;
  cin >> n >> cs >> cf;
  vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(n + 1, vector<int>(2, 0))));
  vector<vector<vector<vector<int>>>> pref(n + 1, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(n + 1, vector<int>(2, 0))));
  dp[2][1][2][0] = 1;
  dp[2][2][1][1] = 1;
  for (int l = 2; l <= n; l++) {
    for (int s = 1; s <= l; s++) {
      for (int f = 1; f <= l; f++) {
        if (s != f && l > 2) {
          dp[l][s][f][0] = ((dp[l][s][f][0] + pref[l - 1][l - 1][f - int(f > s)][1] - pref[l - 1][s - 1][f - int(f > s)][1]) + md) % md;
          dp[l][s][f][1] = (dp[l][s][f][1] + pref[l - 1][s - 1][f - int(f > s)][0]) % md;
        }
        pref[l][s][f][0] = (pref[l][s - 1][f][0] + dp[l][s][f][0]) % md;
        pref[l][s][f][1] = (pref[l][s - 1][f][1] + dp[l][s][f][1]) % md;
      }
    }
  }
  cout << (dp[n][cs][cf][0] + dp[n][cs][cf][1]) % md << '\n';
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...