제출 #255510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255510		rama_pang	Boat (APIO16_boat)	C++14	100 / 100	427 ms	4512 KiB

boat

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N;
  cin >> N;
  vector<int> X = {0};
  vector<int> A(N + 1), B(N + 1);
  for (int i = 1; i <= N; i++) {
    cin >> A[i] >> B[i];
    X.emplace_back(A[i]);
    X.emplace_back(B[i] + 1);
  }
  sort(begin(X), end(X));
  X.erase(unique(begin(X), end(X)), end(X));
  for (int i = 1; i <= N; i++) {
    A[i] = lower_bound(begin(X), end(X), A[i]) - begin(X);
    B[i] = upper_bound(begin(X), end(X), B[i]) - begin(X);
  }

  const int MOD = 1e9 + 7;

  vector<int> inv(N + 1);
  inv[0] = 0, inv[1] = 1;
  for (int i = 2; i <= N; i++) {
    inv[i] = (MOD - 1ll * (MOD / i) * inv[MOD % i] % MOD) % MOD;
  }

  vector<vector<int>> cmb(N + 1, vector<int>(X.size(), 0));
  for (int i = 1; i < (int) X.size(); i++) {
    cmb[0][i] = 1;
    int x = X[i] - X[i - 1];
    for (int j = 1; j <= N; j++) {
      cmb[j][i] = 1ll * cmb[j - 1][i] * (x + j - 1) % MOD * inv[j] % MOD;
    }
  }

  vector<vector<int>> dp(N + 1, vector<int>(X.size(), 0));
  dp[0] = vector<int>(X.size(), 1);
  for (int i = 1; i <= N; i++) {
    dp[i][0] = 1;
    for (int j = 1; j < (int) X.size(); j++) { // [X[j - 1], X[j])
      dp[i][j] = dp[i][j - 1];
      for (int k = i, cnt = 0; k > 0; k--) if (A[k] < j && j <= B[k]) {
        dp[i][j] += 1ll * cmb[++cnt][j] * dp[k - 1][j - 1] % MOD;
        if (dp[i][j] >= MOD) dp[i][j] -= MOD;
      }
    }
  }

  cout << ((dp[N][(int) X.size() - 1] - 1 + MOD) % MOD) << "\n";
  return 0;
}

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