Submission #885993

#	Time	Username	Problem	Language	Result	Execution time	Memory
885993		NeroZein	Boat (APIO16_boat)	C++17	0 / 100	1 ms	600 KiB

boat

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int md = (int) 1e9 + 7; 
const int N = 502;

int iv[N], f1[N], f2[N];
long long a[N], b[N];
long long len[N * 2];
int dp[N][N * 2]; 

inline void add(int& x, int y) {
  x += y;
  if (x >= md) x -= md;
  if (x < 0) x += md; 
}

inline int mul(int x, int y) {
  return (int) ((long long) x * y % md);
}

inline int C(int n, int k) {
  return mul(f1[n], mul(f2[k], f2[n - k]));
}

void bldmd() {
  iv[1] = 1;
  for (int i = 2; i < N; i++) {
    iv[i] = md - mul(md / i, iv[md % i]);
  }
  f1[0] = f2[0] = 1;
  for (int i = 1; i < N; i++) {
    f1[i] = mul(f1[i - 1], i);
    f2[i] = mul(f2[i - 1], iv[i]);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  bldmd(); 
  int n;
  cin >> n;
  vector<long long> c = {0};
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i]; 
    c.push_back(a[i]);
    c.push_back(b[i]);
  }
  sort(c.begin(), c.end());
  c.resize(unique(c.begin(), c.end()) - c.begin()); 
  for (int i = 1; i < (int) c.size(); ++i) {
    len[i] = c[i] - c[i - 1]; 
  }
  for (int i = 1; i <= n; ++i) {
    a[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin();
    b[i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin();
  }
  dp[1][0] = 1; 
  for (int ind = 1; ind <= n; ++ind) {
    for (int last = 0; last <= n * 2; ++last) {
      add(dp[ind + 1][last], dp[ind][last]); 
      for (int new_last = max(a[ind], (long long) last + 1); new_last <= b[ind]; ++new_last) {
        for (int j = ind; j <= n; ++j) {
          add(dp[j + 1][new_last], mul(dp[ind][last], C(len[new_last], j - ind + 1))); 
        }
      }
    }
  }
  int ans = 0; 
  for (int last = 0; last <= n * 2; ++last) {
    add(ans, dp[n + 1][last]); 
  }
  add(ans, -1); 
  cout << ans << '\n'; 
  return 0;
}

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