Submission #00203

ソースコード

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
 
using i64 = int64_t;
const int M = 3e6;
const i64 mod = 1e9 + 7;
vector<i64> fac(M), inv(M);
 
i64 modpow(i64 a, i64 x) {
  if (x == 0) {
    return 1;
  } else if (x == 1) {
    return a;
  } else if (x & 1) {
    return a * modpow(a, x - 1) % mod;
  } else {
    return modpow(a * a % mod, x / 2);
  }
}
 
i64 cmb(i64 n, i64 r) { return fac[n] * inv[r] % mod * inv[n - r] % mod; }
 
int main() {
 
  fac[0] = fac[1] = 1;
  for (int i = 2; i < M; i++) {
    fac[i] = fac[i - 1] * i % mod;
  }
  rep(i, M) inv[i] = modpow(fac[i], mod - 2);
 
  int h, w, n;
  cin >> h >> w >> n;
  vector<pair<int, int>> v(n);
  rep(i, n) cin >> v[i].first >> v[i].second;
  sort(v.begin(), v.end(), [&](const auto &l, const auto &r) {
    return l.first + l.second < r.first + r.second;
  });
  v.push_back({w - 1, h - 1});
  auto pre = make_pair(0, 0);
  i64 ans = 1;
  for (auto p : v) {
    // assert(pre.first <= p.first);
    // assert(pre.second <= p.second);
    auto a = p.first - pre.first, b = p.second - pre.second;
    (ans *= cmb(a + b, a)) %= mod;
    pre = p;
  }
  cout << ans << endl;
  return 0;
}

ステータス

項目	データ
問題	0006 - 寄り道
ユーザー名	ia7ck
投稿日時	2018-11-24 15:25:22
言語	C++14
状態	Runtime Error
得点	0
ソースコード長	1302 Byte
最大実行時間	1607 ms
最大メモリ使用量	47520 KB

セット

	セット	得点	Cases
1	ALL	0 / 400	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
input01.in	AC	426 ms	47452 KB	1
input02.in	AC	429 ms	47260 KB	1
input03.in	AC	418 ms	47316 KB	1
input04.in	RE	1607 ms	47248 KB	1
input05.in	RE	430 ms	47320 KB	1
input06.in	AC	427 ms	47392 KB	1
input07.in	RE	432 ms	47324 KB	1
input08.in	RE	433 ms	47392 KB	1
input09.in	AC	424 ms	47456 KB	1
input10.in	AC	430 ms	47388 KB	1
input11.in	AC	418 ms	47452 KB	1
input12.in	AC	440 ms	47520 KB	1
input13.in	RE	422 ms	47456 KB	1
input14.in	RE	430 ms	47404 KB	1
input15.in	AC	435 ms	47344 KB	1
input16.in	AC	438 ms	47412 KB	1
input17.in	AC	429 ms	47344 KB	1
input18.in	AC	422 ms	47412 KB	1
input19.in	AC	428 ms	47476 KB	1
input20.in	AC	437 ms	47412 KB	1
sample.in	AC	433 ms	47348 KB	1