oj.uz

Submission #257029

# Submission time Handle Problem Language Result Execution time Memory
257029 2020-08-03T14:15:25 Z EntityIT Boat (APIO16_boat) C++14
9 / 100
 541 ms 3452 KB 
#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 = 0; amount < SZ(g); ++amount) {
      for (int j = 1; j <= min(amount + 1, n); ++j) {
        g[amount] += binomials_2[j] * binomials[amount][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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 3328 KB Output is correct
2 Correct 535 ms 3328 KB Output is correct
3 Correct 541 ms 3408 KB Output is correct
4 Correct 532 ms 3412 KB Output is correct
5 Correct 534 ms 3448 KB Output is correct
6 Correct 532 ms 3408 KB Output is correct
7 Correct 528 ms 3448 KB Output is correct
8 Correct 530 ms 3448 KB Output is correct
9 Correct 528 ms 3328 KB Output is correct
10 Correct 530 ms 3448 KB Output is correct
11 Correct 530 ms 3328 KB Output is correct
12 Correct 531 ms 3452 KB Output is correct
13 Correct 530 ms 3448 KB Output is correct
14 Correct 533 ms 3452 KB Output is correct
15 Correct 530 ms 3448 KB Output is correct
16 Correct 95 ms 1664 KB Output is correct
17 Correct 104 ms 1792 KB Output is correct
18 Correct 99 ms 1664 KB Output is correct
19 Correct 104 ms 1912 KB Output is correct
20 Correct 102 ms 1664 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 3328 KB Output is correct
2 Correct 535 ms 3328 KB Output is correct
3 Correct 541 ms 3408 KB Output is correct
4 Correct 532 ms 3412 KB Output is correct
5 Correct 534 ms 3448 KB Output is correct
6 Correct 532 ms 3408 KB Output is correct
7 Correct 528 ms 3448 KB Output is correct
8 Correct 530 ms 3448 KB Output is correct
9 Correct 528 ms 3328 KB Output is correct
10 Correct 530 ms 3448 KB Output is correct
11 Correct 530 ms 3328 KB Output is correct
12 Correct 531 ms 3452 KB Output is correct
13 Correct 530 ms 3448 KB Output is correct
14 Correct 533 ms 3452 KB Output is correct
15 Correct 530 ms 3448 KB Output is correct
16 Correct 95 ms 1664 KB Output is correct
17 Correct 104 ms 1792 KB Output is correct
18 Correct 99 ms 1664 KB Output is correct
19 Correct 104 ms 1912 KB Output is correct
20 Correct 102 ms 1664 KB Output is correct
21 Incorrect 420 ms 3200 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 3328 KB Output is correct
2 Correct 535 ms 3328 KB Output is correct
3 Correct 541 ms 3408 KB Output is correct
4 Correct 532 ms 3412 KB Output is correct
5 Correct 534 ms 3448 KB Output is correct
6 Correct 532 ms 3408 KB Output is correct
7 Correct 528 ms 3448 KB Output is correct
8 Correct 530 ms 3448 KB Output is correct
9 Correct 528 ms 3328 KB Output is correct
10 Correct 530 ms 3448 KB Output is correct
11 Correct 530 ms 3328 KB Output is correct
12 Correct 531 ms 3452 KB Output is correct
13 Correct 530 ms 3448 KB Output is correct
14 Correct 533 ms 3452 KB Output is correct
15 Correct 530 ms 3448 KB Output is correct
16 Correct 95 ms 1664 KB Output is correct
17 Correct 104 ms 1792 KB Output is correct
18 Correct 99 ms 1664 KB Output is correct
19 Correct 104 ms 1912 KB Output is correct
20 Correct 102 ms 1664 KB Output is correct
21 Incorrect 420 ms 3200 KB Output isn't correct
22 Halted 0 ms 0 KB -