oj.uz

Submission #679842

# Submission time Handle Problem Language Result Execution time Memory
679842 2023-01-09T12:24:21 Z peijar Kangaroo (CEOI16_kangaroo) C++17
51 / 100
 2000 ms 63948 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <const int32_t MOD> struct ModInt {
  int32_t x;
  ModInt() : x(0) {}
  ModInt(long long u) : x(u % MOD) {
    if (x < 0)
      x += MOD;
  }
  friend bool operator==(const ModInt &a, const ModInt &b) {
    return a.x == b.x;
  }
  friend bool operator!=(const ModInt &a, const ModInt &b) {
    return a.x != b.x;
  }
  friend bool operator<(const ModInt &a, const ModInt &b) { return a.x < b.x; }
  friend bool operator>(const ModInt &a, const ModInt &b) { return a.x > b.x; }
  friend bool operator<=(const ModInt &a, const ModInt &b) {
    return a.x <= b.x;
  }
  friend bool operator>=(const ModInt &a, const ModInt &b) {
    return a.x >= b.x;
  }
  static ModInt sign(long long k) {
    return ((k & 1) ? ModInt(MOD - 1) : ModInt(1));
  }

  ModInt &operator+=(const ModInt &m) {
    x += m.x;
    if (x >= MOD)
      x -= MOD;
    return *this;
  }
  ModInt &operator-=(const ModInt &m) {
    x -= m.x;
    if (x < 0LL)
      x += MOD;
    return *this;
  }
  ModInt &operator*=(const ModInt &m) {
    x = (1LL * x * m.x) % MOD;
    return *this;
  }

  friend ModInt operator-(const ModInt &a) {
    ModInt res(a);
    if (res.x)
      res.x = MOD - res.x;
    return res;
  }
  friend ModInt operator+(const ModInt &a, const ModInt &b) {
    return ModInt(a) += ModInt(b);
  }
  friend ModInt operator-(const ModInt &a, const ModInt &b) {
    return ModInt(a) -= ModInt(b);
  }
  friend ModInt operator*(const ModInt &a, const ModInt &b) {
    return ModInt(a) *= ModInt(b);
  }

  static long long fp(long long u, long long k) {
    long long res = 1LL;
    while (k > 0LL) {
      if (k & 1LL)
        res = (res * u) % MOD;
      u = (u * u) % MOD;
      k /= 2LL;
    }
    return res;
  }

  static constexpr int mod() { return MOD; }

  ModInt fastpow(long long k) { return ModInt(fp(x, k)); }
  ModInt inv() {
    assert(x);
    return ModInt(fp(x, MOD - 2));
  }
  ModInt &operator/=(const ModInt &m) { return *this *= ModInt(m).inv(); }
  friend ModInt operator/(const ModInt &a, const ModInt &b) {
    return ModInt(a) *= ModInt(b).inv();
  }

  friend ostream &operator<<(ostream &out, const ModInt &a) {
    return out << a.x;
  }
  friend istream &operator>>(istream &in, ModInt &a) { return in >> a.x; }
};

const int MOD = 1e9 + 7;
using Mint = ModInt<MOD>;

const int MAXN = 201;

Mint A[MAXN][MAXN][MAXN], D[MAXN][MAXN][MAXN];

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N, cs, ce;
  cin >> N >> cs >> ce;
  --cs, --ce;
  A[1][0][0] = D[1][0][0] = 1;
  for (int n = 2; n <= N; ++n)
    for (int start = 0; start < n; ++start)
      for (int end = 0; end < n; ++end)
        if (start != end) {
          for (int nxt = start + 1; nxt < N; ++nxt)
            A[n][start][end] += D[n - 1][nxt - 1][end - (end > start)];
          for (int nxt = 0; nxt < start; ++nxt)
            D[n][start][end] += A[n - 1][nxt][end - (end > start)];
        }
  cout << A[N][cs][ce] + D[N][cs][ce] << endl;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 63808 KB Output is correct
2 Correct 26 ms 63828 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 63808 KB Output is correct
2 Correct 26 ms 63828 KB Output is correct
3 Correct 25 ms 63804 KB Output is correct
4 Correct 26 ms 63876 KB Output is correct
5 Correct 26 ms 63868 KB Output is correct
6 Correct 29 ms 63808 KB Output is correct
7 Correct 26 ms 63828 KB Output is correct
8 Correct 26 ms 63796 KB Output is correct
9 Correct 28 ms 63828 KB Output is correct
10 Correct 27 ms 63876 KB Output is correct
11 Correct 27 ms 63820 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 63808 KB Output is correct
2 Correct 26 ms 63828 KB Output is correct
3 Correct 25 ms 63804 KB Output is correct
4 Correct 26 ms 63876 KB Output is correct
5 Correct 26 ms 63868 KB Output is correct
6 Correct 29 ms 63808 KB Output is correct
7 Correct 26 ms 63828 KB Output is correct
8 Correct 26 ms 63796 KB Output is correct
9 Correct 28 ms 63828 KB Output is correct
10 Correct 27 ms 63876 KB Output is correct
11 Correct 27 ms 63820 KB Output is correct
12 Correct 716 ms 63868 KB Output is correct
13 Correct 578 ms 63864 KB Output is correct
14 Correct 717 ms 63868 KB Output is correct
15 Correct 744 ms 63868 KB Output is correct
16 Correct 729 ms 63948 KB Output is correct
17 Correct 714 ms 63872 KB Output is correct
18 Correct 477 ms 63868 KB Output is correct
19 Correct 700 ms 63868 KB Output is correct
20 Correct 734 ms 63864 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 63808 KB Output is correct
2 Correct 26 ms 63828 KB Output is correct
3 Correct 25 ms 63804 KB Output is correct
4 Correct 26 ms 63876 KB Output is correct
5 Correct 26 ms 63868 KB Output is correct
6 Correct 29 ms 63808 KB Output is correct
7 Correct 26 ms 63828 KB Output is correct
8 Correct 26 ms 63796 KB Output is correct
9 Correct 28 ms 63828 KB Output is correct
10 Correct 27 ms 63876 KB Output is correct
11 Correct 27 ms 63820 KB Output is correct
12 Correct 716 ms 63868 KB Output is correct
13 Correct 578 ms 63864 KB Output is correct
14 Correct 717 ms 63868 KB Output is correct
15 Correct 744 ms 63868 KB Output is correct
16 Correct 729 ms 63948 KB Output is correct
17 Correct 714 ms 63872 KB Output is correct
18 Correct 477 ms 63868 KB Output is correct
19 Correct 700 ms 63868 KB Output is correct
20 Correct 734 ms 63864 KB Output is correct
21 Execution timed out 2085 ms 63828 KB Time limit exceeded
22 Halted 0 ms 0 KB -