Submission #23486

#	Time	Username	Problem	Language	Result	Execution time	Memory
23486		Nirjhor	Boat (APIO16_boat)	C++14	9 / 100	803 ms	10280 KiB

boat

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 505;
const int M = 1005;
const int MOD = 1e9 + 7;

int n, m;
ll a[N], b[N];
ll dp[N][M];
vector <pii> v;
ll x[M], y[M];
vector <int> z[M];
int sz[M];
ll wide[M];
int counter = 1;
ll comb[M][N];
ll inverse[N];

ll bigMod (ll a, ll e) {
  if (e == -1) e = MOD - 2;
  ll r = 1ll; while (e) {
    if (e & 1) r = (r * a) % MOD;
    a = (a * a) % MOD;
    e >>= 1;
  }
  return r;
}

ll call (int at, int range) {
  if (at > n or range > m) return 1;
  if (dp[at][range] != -1) return dp[at][range];
  int pos = 0;
  while (pos < sz[range] and z[range][pos] < at) {
    ++pos;
  }
  ll ret = call(at, range + 1);
  for (int i = pos; i < sz[range]; ++i) {
    int rem = i - pos, cur = z[range][i];
    // cout << rem << " comb ---> " << comb[range][rem] << endl;
    ll add = (comb[range][rem] * call(cur + 1, range + 1)) % MOD;
    ret += add, ret %= MOD;
  }
  return dp[at][range] = ret;
}

ll nCr (ll n, ll r) {
  if (n < r or n < 0 or r < 0) return 0;
  ll res = 1ll;
  for (ll i = n; i >= n - r + 1; --i) {
    res *= i, res %= MOD;
  }
  for (ll i = 1; i <= r; ++i) {
    res *= inverse[i];
    res %= MOD;
  }
  return res;
}

int main (int argc, char const *argv[]) {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%lld %lld", a + i, b + i);
    v.push_back({a[i], 0});
    v.push_back({b[i], 1});
  }
  sort(v.begin(), v.end());
  for (int i = 1; i < n + n; ++i) {
    int one = v[i - 1].second, two = v[i].second;
    int l = v[i - 1].first, r = v[i].first;
    if (!one and !two) {
      --r, ++counter;
      if (l >= r) x[++m] = l, y[m] = r;
    } else if (!one and two) {
      --counter;
      if (l >= r) x[++m] = l, y[m] = r;
    } else if (one and two) {
      ++l, --counter;
      if (l >= r) x[++m] = l, y[m] = r; 
    } else {
      ++l;
      if (counter and l >= r) x[++m] = l, y[m] = r;
      ++counter;
    }
  }
  // for (int i = 1; i <= m; ++i) {
  //   cout << x[i] << " " << y[i] << endl;
  // }
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (a[j] <= x[i] and y[i] <= b[j]) {
        z[i].push_back(j);
        ++sz[i];
      }
    }
    wide[i] = y[i] - x[i] + 1;
  } 
  for (int i = 1; i < N; ++i) {
    inverse[i] = bigMod(i, -1);
  }
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j <= n; ++j) {
      comb[i][j] = nCr(wide[i] + j, j + 1);
    }
  }
  // for (int i = 1; i <= m; ++i) {
  //   cout << i << " --> ";
  //   for (int j : z[i]) cout << j << " ";
  //   cout << endl;
  // } 
  memset(dp, -1, sizeof dp);
  // for (int i = 1; i <= n; ++i) {
  //   for (int j = 1; j <= m; ++j) {
  //     cout << "(" << i << ", " << j << ") ---> " << call(i, j) << endl;
  //   }
  // }
  ll ans = call(1, 1) + MOD - 1;
  printf("%lld\n", ans % MOD);
  return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main(int, const char**)':
boat.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
boat.cpp:67:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", a + i, b + i);
                                     ^

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