Submission #964587

#	Time	Username	Problem	Language	Result	Execution time	Memory
964587		Soumya1	Boat (APIO16_boat)	C++17	100 / 100	1497 ms	12452 KiB

boat

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int dp[2005][501], ndp[2005][501];
int C[2005][501];
int power(int a, int b) {
  int r = 1;
  while (b > 0) {
    if (b & 1) r = (1LL * r * a) % mod;
    a = (1LL * a * a) % mod, b >>= 1;
  }
  return r;
}
void testCase() {
  int n;
  cin >> n;
  vector<int> l(n + 1), r(n + 1), all;
  for (int i = 1; i <= n; i++) {
    cin >> l[i] >> r[i];
    all.push_back(l[i]);
    all.push_back(r[i]);
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  vector<pair<int, int>> ranges;
  vector<int> range_id(all.size());
  for (int i = 0; i < all.size(); i++) {
    if (i > 0 && all[i - 1] + 1 <= all[i] - 1) ranges.push_back({all[i - 1] + 1, all[i] - 1});
    range_id[i] = ranges.size();
    ranges.push_back({all[i], all[i]});
  }
  auto get = [&](int x) {
    return lower_bound(all.begin(), all.end(), x) - all.begin();
  };
  int range_cnt = ranges.size();
  for (int i = 0; i < range_cnt; i++) {
    auto [L, R] = ranges[i];
    C[i][0] = 1;
    C[i][1] = (R - L + 1) % mod;
    for (int j = 2; j <= n; j++) {
      if (j > R - L + 1) C[i][j] = 0;
      else C[i][j] = (1LL * (1LL * C[i][j - 1] * (R - L + 1 - j + 1)) % mod * power(j, mod - 2)) % mod;
    }
  }
  for (int j = 0; j <= range_cnt; j++) dp[j][0] = 1;
  for (int i = 1; i <= n; i++) {
    int L = range_id[get(l[i])], R = range_id[get(r[i])];
    for (int j = L; j <= R; j++) {
      for (int k = 1; k <= n; k++) {
        ndp[j][k] = dp[j][k - 1];
        ndp[j + 1][0] += (1LL * ndp[j][k] * C[j][k]) % mod;
        if (ndp[j + 1][0] >= mod) ndp[j + 1][0] -= mod;
      }
      ndp[j + 1][0] += ndp[j][0];
      if (ndp[j + 1][0] >= mod) ndp[j + 1][0] -= mod;
    }
    for (int j = R + 1; j < range_cnt; j++) {
      ndp[j + 1][0] += ndp[j][0];
      if (ndp[j + 1][0] >= mod) ndp[j + 1][0] -= mod;
    }
    for (int j = 0; j <= range_cnt; j++) {
      for (int k = 0; k <= n; k++) {
        dp[j][k] += ndp[j][k];
        if (dp[j][k] >= mod) dp[j][k] -= mod;
        ndp[j][k] = 0;
      }
    }
  }
  int ans = dp[range_cnt][0] - 1;
  if (ans < 0) ans += mod;
  cout << ans << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void testCase()':
boat.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int i = 0; i < all.size(); i++) {
      |                   ~~^~~~~~~~~~~~

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