Submission #1104417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104417		LucaLucaM	Boat (APIO16_boat)	C++17	0 / 100	2 ms	336 KiB

boat

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define int ll
#warning That's not the baby, that's my baby

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

const int INF = 1e9;
const int mod = 1e9 + 7;
const int NMAX = 500;

int power(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) {
      ret = (ll) ret * a % mod;
    }
    a = (ll) a * a % mod;
    b >>= 1;
  }
  return ret;
}

int fac[NMAX + 1];
int ifac[NMAX + 1];

int nondec(int n, int k) { // 1 <= x1 <= x2 <= ... <= xk <= n
  // xi += i-1 => 1 <= x1 < x2 < ... < xk <= n + k - 1
  // C(n + k - 1, k)
  int answer = 1;
  for (int i = n; i < n + k; i++) {
    answer = (ll) answer * i % mod;
  }
  answer = (ll) answer * ifac[k] % mod;
  return answer;
}

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

  int n;
  std::cin >> n;

  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = (ll) fac[i - 1] * i % mod;
  }
  ifac[n] = power(fac[n], mod - 2);
  for (int i = n - 1; i >= 0; i--) {
    ifac[i] = (ll) ifac[i + 1] * (i + 1) % mod;
  } 

  std::vector<int> a(n + 1), b(n + 1);
  std::vector<int> norm;

  for (int i = 1; i <= n; i++) {
    std::cin >> a[i] >> b[i];
  }

  for (int i = 1; i <= n; i++) {
    a[i] = std::max(a[i], a[i - 1]);
    norm.push_back(a[i]);
  }
  norm.push_back(b[n]);
  for (int i = n - 1; i  > 0; i--) {
    b[i] = std::min(b[i], b[i + 1]);
    norm.push_back(b[i]);
  }

  std::sort(norm.begin(), norm.end());
  norm.erase(std::unique(norm.begin(), norm.end()), norm.end());

  norm.push_back(norm.back() + 1);
  
  std::vector<std::vector<int>> dp(n + 1, std::vector<int>((int) norm.size() + 3, 0));

  // for (const auto &x : norm) {
  //   std::cout << debug(x);
  // }

  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    int l = norm[0];
    int r = norm[1] - 1;
    if (a[i] <= l && r <= b[1]) {
      dp[i][0] = nondec(r - l + 1, i);
    } else {
      dp[i][0] = 0;
    }
  }

  for (int i = 1; i <= n; i++) {
    for (int index = 1; index + 1 < (int) norm.size(); index++) {
      int l = norm[index], r = norm[index + 1] - 1;
      for (int j = i; j > 0; j--) {
        if (a[i] <= l && r <= b[j]) {
          // [j, i] sunt toate in [l, r] si < j e in < l
          for (int k = 0; k < index; k++) {
            dp[i][index] += (ll) dp[j - 1][k] * nondec(r - l + 1, i - j + 1) % mod;
          }
          dp[i][index] %= mod;
        }
      }
    }
  }

  ll answer = 0;
  for (int index = 0; index + 1 < (int) norm.size(); index++) {
    answer += dp[n][index];
  }
  std::cout << answer % mod;

  return 0;
}

Compilation message (stderr)

boat.cpp:6:2: warning: #warning That's not the baby, that's my baby [-Wcpp]
    6 | #warning That's not the baby, that's my baby
      |  ^~~~~~~

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