제출 #23489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
23489		Nirjhor	Boat (APIO16_boat)	C++14	58 / 100	2000 ms	11336 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) {
    // cout << rem << " comb ---> " << comb[range][rem] << endl;
    ret += comb[range][i - pos] * call(z[range][i] + 1, range + 1);
    ret %= MOD;
  }
  return dp[at][range] = ret;
}

ll nCr (ll n, ll r) {
  if (n < r) return 0;
  ll res = 1ll;
  for (ll i = n, j = 1; i >= n - r + 1; --i, ++j) {
    res *= i, res %= MOD;
    res *= inverse[j], 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;
      // cout << "yo " << i << " " << m << endl;
      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, --r;
      if (counter and l <= r) x[++m] = l, y[m] = r;
      ++counter;
    }
  }
  // cout << m << endl;
  // 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;
}

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main(int, const char**)':
boat.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
boat.cpp:63: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: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42