Submission #257034

#	Time	Username	Problem	Language	Result	Execution time	Memory
257034		EntityIT	Boat (APIO16_boat)	C++14	100 / 100	1766 ms	3456 KiB

boat

#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

template<int Mod>
struct ModInt {
  int a;
  ModInt(int t_a = 0) {
    a = (t_a < Mod ? (t_a < 0 ? t_a + Mod : t_a) : t_a - Mod);
  }
  friend istream& operator>>(istream& in_stream, ModInt& o) {
    in_stream >> o.a;
    o.a = (o.a < Mod ? (o.a < 0 ? o.a + Mod : o.a) : o.a - Mod);
    return in_stream;
  }
  friend ostream& operator<<(ostream& out_stream, const ModInt& o) {
    out_stream << o.a;
    return out_stream;
  }

  bool operator!() const { return !a; }
  explicit operator bool() const { return !!a; }

  ModInt operator-() const { return ModInt() - *this; }
  ModInt operator+(const ModInt& o) const { return ModInt(a + o.a); }
  ModInt operator-(const ModInt& o) const { return ModInt(a - o.a); }
  ModInt operator*(const ModInt& o) const { return ModInt(static_cast<int>(static_cast<int64_t>(a) * o.a % Mod)); }
  ModInt operator/(const ModInt& o) const { return *this * o.Inverse(); }
  ModInt& operator+=(const ModInt& o) { return *this = *this + o; }
  ModInt& operator-=(const ModInt& o) { return *this = *this - o; }
  ModInt& operator*=(const ModInt& o) { return *this = *this * o; }
  ModInt& operator/=(const ModInt& o) { return *this = *this / o; }
  ModInt& operator++() { return *this = *this + ModInt(1); }
  ModInt& operator--() { return *this = *this - ModInt(1); }
  ModInt Inverse() const { return Power(Mod - 2); }
  template<class T>
  ModInt Power(T exp) const {
    ModInt ret(1), c = *this;
    for (; exp; exp >>= 1, c *= c) {
      if (exp & 1) {
        ret *= c;
      }
    }
    return ret;
  }
};
using Mint = ModInt<static_cast<int>(1e9) + 7>;

constexpr int kMod = static_cast<int>(1e9) + 7;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  int n_schools; cin >> n_schools;
  vec<pair<int, int>, 1> ranges(n_schools);
  vec<int, 1> marks; marks.reserve(n_schools << 1);
  for (auto& range : ranges) {
    cin >> range.first >> range.second; ++range.second;
    marks.emplace_back(range.first);
    marks.emplace_back(range.second);
  }
  sort(ALL(marks)); marks.erase(unique(ALL(marks)), marks.end());

  vec<Mint, 2> binomials(n_schools + 1, n_schools + 1);
  binomials[0][0] = Mint(1);
  for (int i = 1; i < SZ(binomials); ++i) {
    for (int j = 0; j <= i; ++j) {
      binomials[i][j] = (j ? binomials[i - 1][j - 1] : Mint()) + binomials[i - 1][j];
    }
  }

  vec<Mint, 1> inverses(n_schools + 1);
  inverses[1] = Mint(1);
  for (int i = 2; i < SZ(inverses); ++i) {
    inverses[i] = inverses[kMod % i] * Mint(kMod - kMod / i);
  }

  vec<Mint, 2> f(SZ(marks), n_schools + 1);
  f[0][0] = Mint(1);
  for (int i = 1; i < SZ(marks); ++i) {
    int const n = marks[i] - marks[i - 1];
    vec<Mint, 1> binomials_2(min(n_schools, n) + 1);
    binomials_2[0] = Mint(1);
    for (int j = 1; j < SZ(binomials_2); ++j) {
      binomials_2[j] = binomials_2[j - 1] * Mint(n - j + 1) * inverses[j];
    }
    vec<Mint, 1> g(n_schools + 1);
    for (int amount = 1; amount < SZ(g); ++amount) {
      for (int j = 1; j <= min(amount, n); ++j) {
        g[amount] += binomials_2[j] * binomials[amount - 1][j - 1];
      }
    }

    for (int j = 0; j <= n_schools; ++j) {
      f[i][j] += f[i - 1][j];

      if (!j || marks[i] <= ranges[j - 1].first || ranges[j - 1].second <= marks[i - 1]) {
        continue;
      }
      int amount = 0;
      for (int prev_j = j - 1; ~prev_j; --prev_j) {
        amount += ranges[prev_j].first <= marks[i - 1] && marks[i] <= ranges[prev_j].second;
        f[i][j] += f[i - 1][prev_j] * g[amount];
      }
    }
  }

  cout << accumulate(1 + ALL(f.back()), Mint()) << '\n';

  return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42