Submission #1326237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326237		apxo	Boat (APIO16_boat)	C++20	100 / 100	420 ms	440 KiB

boat

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 505;
const int mod = 1e9 + 7;
int n, a[maxn], b[maxn];
int inv[maxn];
vector<int> cmp;
int f[maxn];

int add(int x, int y) {
  if (y < 0) y += mod;
  x += y;
  if (x >= mod) x -= mod;
  return x;
}

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

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
    cmp.push_back(a[i]);
    cmp.push_back(b[i] + 1);
  }
  cmp.push_back(0);
  sort(cmp.begin(), cmp.end());
  cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
  int sz = (int)cmp.size() - 1;
  f[0] = 1;
  for (int i = 1; i < sz; ++i) {
    int l = cmp[i + 1] - cmp[i];
    for (int j = n; j; --j) {
      if (cmp[i] >= a[j] and cmp[i] <= b[j]) {
        int nf = 0;
        int cnk = 1;
        int cnt = 0;
        for (int k = j; k; --k) {
          if (cmp[i] >= a[k] and cmp[i] <= b[k]) {
            cnk = 1ll * cnk * inv[cnt + 1] % mod * (l + cnt) % mod;
            ++cnt;
          }
          nf = add(nf, 1ll * f[k - 1] * cnk % mod);
        }
        f[j] = add(f[j], nf);
      }   
    }
  }
  int res = 0;
  for (int i = 1; i <= n; ++i) res = add(res, f[i]);
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  inv[0] = 1;
  for (int i = 1; i < maxn; ++i) inv[i] = power(i, mod - 2);
  
  solve();

  return 0;
}

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