Submission #725805

#	Time	Username	Problem	Language	Result	Execution time	Memory
725805		quiet_space	Boat (APIO16_boat)	C++14	100 / 100	294 ms	340 KiB

boat

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
const int maxn = 505;
const int mod = 1000000007;
inline void inc (int&x, int y) { (x += y) >= mod ? x -= mod : x; }
int l[maxn], r[maxn], totb, b[maxn<<1], inv[maxn], c[maxn], g[maxn];
int main (void) {
  int n = read();
  inv[1] = 1;
  FOR(i,2,n) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
  FOR(i,1,n) b[++ totb] = l[i] = read(), b[++ totb] = r[i] = read() + 1;
  std::sort(b+1, b+totb+1);
  totb = std::unique(b+1, b+totb+1) - b - 1;
  FOR(i,1,n) l[i] = std::lower_bound (b+1, b+totb+1, l[i]) - b, r[i] = std::lower_bound (b+1, b+totb+1, r[i]) - b;
  c[0] = g[0] = 1;
  FOR(j,1,totb-1) {
    int len = b[j + 1] - b[j];
    FOR(i,1,n) c[i] = 1ll * c[i-1] * (len + i - 1) % mod * inv[i] % mod;
    ROF(i,n,1) if(l[i] <= j && j < r[i]) {
      int f = 0, cnt = 1;
      ROF(k,i-1,0) {
        f = (f + 1ll * c[cnt] * g[k]) % mod;
        if(l[k] <= j && j < r[k]) ++ cnt;
      }
      inc (g[i], f);
    }
  }
  int ans = 0;
  FOR(i,1,n) inc (ans, g[i]);
  printf("%d\n", ans);
  return 0;
}

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