結果
| 問題 | No.801 エレベーター |
| ユーザー |
 kyawashell
|
| 提出日時 | 2020-06-22 13:36:10 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 152 ms / 2,000 ms |
| コード長 | 7,597 bytes |
| コンパイル時間 | 1,027 ms |
| コンパイル使用メモリ | 130,552 KB |
| 実行使用メモリ | 73,728 KB |
| 最終ジャッジ日時 | 2024-05-07 22:01:09 |
| 合計ジャッジ時間 | 4,802 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 3 ms
5,376 KB |
| testcase_04 | AC | 3 ms
5,376 KB |
| testcase_05 | AC | 3 ms
5,376 KB |
| testcase_06 | AC | 3 ms
5,376 KB |
| testcase_07 | AC | 3 ms
5,376 KB |
| testcase_08 | AC | 3 ms
5,376 KB |
| testcase_09 | AC | 3 ms
5,376 KB |
| testcase_10 | AC | 3 ms
5,376 KB |
| testcase_11 | AC | 3 ms
5,376 KB |
| testcase_12 | AC | 3 ms
5,376 KB |
| testcase_13 | AC | 150 ms
73,600 KB |
| testcase_14 | AC | 150 ms
73,728 KB |
| testcase_15 | AC | 149 ms
73,600 KB |
| testcase_16 | AC | 150 ms
73,600 KB |
| testcase_17 | AC | 150 ms
73,472 KB |
| testcase_18 | AC | 150 ms
73,472 KB |
| testcase_19 | AC | 148 ms
73,472 KB |
| testcase_20 | AC | 151 ms
73,344 KB |
| testcase_21 | AC | 151 ms
73,600 KB |
| testcase_22 | AC | 152 ms
73,600 KB |
| testcase_23 | AC | 134 ms
73,472 KB |
| testcase_24 | AC | 133 ms
73,472 KB |
| testcase_25 | AC | 136 ms
73,600 KB |
| testcase_26 | AC | 133 ms
73,600 KB |
| testcase_27 | AC | 133 ms
73,472 KB |
| testcase_28 | AC | 127 ms
73,600 KB |
ソースコード
#include <stdint.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
using default_counter_t = int64_t;
// macro
#define let auto const &
#define overload4(a, b, c, d, name, ...) name
#define rep1(n) \
for (default_counter_t i = 0, end_i = default_counter_t(n); i < end_i; ++i)
#define rep2(i, n) \
for (default_counter_t i = 0, end_##i = default_counter_t(n); i < end_##i; \
++i)
#define rep3(i, a, b) \
for (default_counter_t i = default_counter_t(a), \
end_##i = default_counter_t(b); \
i < end_##i; ++i)
#define rep4(i, a, b, c) \
for (default_counter_t i = default_counter_t(a), \
end_##i = default_counter_t(b); \
i < end_##i; i += default_counter_t(c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) \
for (default_counter_t i = default_counter_t(n) - 1; i >= 0; --i)
#define rrep2(i, n) \
for (default_counter_t i = default_counter_t(n) - 1; i >= 0; --i)
#define rrep3(i, a, b) \
for (default_counter_t i = default_counter_t(b) - 1, \
begin_##i = default_counter_t(a); \
i >= begin_##i; --i)
#define rrep4(i, a, b, c) \
for (default_counter_t \
i = (default_counter_t(b) - default_counter_t(a) - 1) / \
default_counter_t(c) * default_counter_t(c) + \
default_counter_t(a), \
begin_##i = default_counter_t(a); \
i >= begin_##i; i -= default_counter_t(c))
#define rrep(...) \
overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define ALL(f, c, ...) \
(([&](decltype((c)) cccc) { \
return (f)(std::begin(cccc), std::end(cccc), ##__VA_ARGS__); \
})(c))
// function
template <class C>
constexpr C &Sort(C &a) {
std::sort(std::begin(a), std::end(a));
return a;
}
template <class C>
constexpr auto &Min(C const &a) {
return *std::min_element(std::begin(a), std::end(a));
}
template <class C>
constexpr auto &Max(C const &a) {
return *std::max_element(std::begin(a), std::end(a));
}
template <class C>
constexpr auto Total(C const &c) {
return std::accumulate(std::begin(c), std::end(c), C(0));
}
template <typename T>
auto CumSum(std::vector<T> const &v) {
std::vector<T> a(v.size() + 1, T(0));
for (std::size_t i = 0; i < a.size() - size_t(1); ++i) a[i + 1] = a[i] + v[i];
return a;
}
template <typename T>
constexpr bool ChMax(T &a, T const &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T>
constexpr bool ChMin(T &a, T const &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
void In(void) { return; }
template <typename First, typename... Rest>
void In(First &first, Rest &... rest) {
cin >> first;
In(rest...);
return;
}
template <class T, typename I>
void VectorIn(vector<T> &v, const I n) {
v.resize(size_t(n));
rep(i, v.size()) cin >> v[i];
}
void Out(void) {
cout << "\n";
return;
}
template <typename First, typename... Rest>
void Out(First first, Rest... rest) {
cout << first << " ";
Out(rest...);
return;
}
constexpr auto yes(const bool c) { return c ? "yes" : "no"; }
constexpr auto Yes(const bool c) { return c ? "Yes" : "No"; }
constexpr auto YES(const bool c) { return c ? "YES" : "NO"; }
// http://koturn.hatenablog.com/entry/2018/08/01/010000
template <typename T, typename U>
inline std::vector<U> MakeNdVector(T n, U val) noexcept {
static_assert(std::is_integral<T>::value,
"[MakeNdVector] The 1st argument must be an integer");
return std::vector<U>(std::forward<T>(n), std::forward<U>(val));
}
template <typename T, typename... Args>
inline decltype(auto) MakeNdVector(T n, Args &&... args) noexcept {
static_assert(std::is_integral<T>::value,
"[MakeNdVector] The 1st argument must be an integer");
return std::vector<decltype(MakeNdVector(std::forward<Args>(args)...))>(
std::forward<T>(n), MakeNdVector(std::forward<Args>(args)...));
}
template <typename T, std::size_t N,
typename std::enable_if<(N > 0), std::nullptr_t>::type = nullptr>
struct NdvectorImpl {
using type = std::vector<typename NdvectorImpl<T, N - 1>::type>;
}; // struct ndvector_impl
template <typename T>
struct NdvectorImpl<T, 1> {
using type = std::vector<T>;
}; // struct ndvector_impl
template <typename T, std::size_t N>
using NdVector = typename NdvectorImpl<T, N>::type;
#ifdef USE_STACK_TRACE_LOGGER
#ifdef __clang__
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Weverything"
#include <glog/logging.h>
#pragma clang diagnostic pop
#endif //__clang__
#endif // USE_STACK_TRACE_LOGGER
template <int64_t Mod>
struct ModInt {
int64_t x;
ModInt() : x(0) {}
ModInt(int64_t y) : x(y >= 0 ? y % Mod : (Mod - (-y) % Mod) % Mod) {}
ModInt &operator+=(const ModInt &p) {
if ((x += p.x) >= Mod) x -= Mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if ((x += Mod - p.x) >= Mod) x -= Mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = int64_t(1LL * x * p.x % Mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.Inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt Inverse() const {
int64_t a = x, b = Mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt Pow(int64_t n) const {
ModInt ret(1), mul(x);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt<Mod>(t);
return (is);
}
static int64_t GetMod() { return Mod; }
};
using Event = pair<int64_t, int64_t>;
signed main(int argc, char *argv[]) {
(void)argc;
#ifdef USE_STACK_TRACE_LOGGER
google::InitGoogleLogging(argv[0]);
google::InstallFailureSignalHandler();
#else
(void)argv;
#endif // USE_STACK_TRACE_LOGGER
int64_t N, M, K;
In(N, M, K);
vector<int64_t> L(M), R(M);
rep(i, M) { In(L[i], R[i]); }
using Mi = ModInt<1000000007>;
auto dp = MakeNdVector(K + 1, N + 1, Mi(0));
dp[0][1] = 1;
rep(k, K) {
auto cum = MakeNdVector(N + 2, Mi(0));
rep(i, 1, N + 1) { cum[i + 1] += cum[i] + dp[k][i]; }
rep(i, M) {
dp[k + 1][L[i]] += cum[R[i] + 1] - cum[L[i]];
if (R[i] + 1 <= N) {
dp[k + 1][R[i] + 1] -= cum[R[i] + 1] - cum[L[i]];
}
}
rep(i, 1, N) { dp[k + 1][i + 1] += dp[k + 1][i]; }
}
cout << dp[K][N] << endl;
return EXIT_SUCCESS;
}