#898600 (C++23) No.2402 Dirty Stairs and Shoes

提出ソース

結果

問題	No.2402 Dirty Stairs and Shoes
ユーザー	AC2K
提出日時	2023-08-04 22:30:04
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	116 ms / 2,000 ms
コード長	6,221 bytes
コンパイル時間	3,446 ms
コンパイル使用メモリ	252,936 KB
実行使用メモリ	9,216 KB
最終ジャッジ日時	2024-05-10 07:22:16
合計ジャッジ時間	5,087 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	65 ms 7,408 KB
testcase_04	AC	6 ms 5,376 KB
testcase_05	AC	116 ms 9,216 KB
testcase_06	AC	29 ms 5,376 KB
testcase_07	AC	10 ms 5,376 KB
testcase_08	AC	14 ms 5,376 KB
testcase_09	AC	29 ms 5,376 KB
testcase_10	AC	56 ms 6,868 KB
testcase_11	AC	33 ms 5,632 KB
testcase_12	AC	13 ms 5,376 KB
testcase_13	AC	8 ms 5,376 KB
testcase_14	AC	10 ms 5,376 KB
testcase_15	AC	7 ms 5,376 KB
testcase_16	AC	4 ms 5,376 KB
testcase_17	AC	9 ms 5,376 KB
testcase_18	AC	7 ms 5,376 KB
testcase_19	AC	10 ms 5,376 KB
testcase_20	AC	8 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	5 ms 5,376 KB
testcase_23	AC	5 ms 5,376 KB
testcase_24	AC	6 ms 5,376 KB
testcase_25	AC	9 ms 5,376 KB
testcase_26	AC	6 ms 5,376 KB
testcase_27	AC	9 ms 5,376 KB
testcase_28	AC	8 ms 5,376 KB
testcase_29	AC	5 ms 5,376 KB
testcase_30	AC	3 ms 5,376 KB
testcase_31	AC	10 ms 5,376 KB
testcase_32	AC	5 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	5 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 2 "library/src/stream.hpp"
#include <ctype.h>
#include <stdio.h>
#include <string>
#line 2 "library/src/internal/type_traits.hpp"
#include <iostream>
#include <limits>
#include <numeric>
#include <typeinfo>
namespace kyopro {
namespace internal {
/*
 * @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
 */
template <typename... Args> struct first_enabled {};

template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
    using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
    : first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
    using type = T;
};

template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;

template <int dgt> struct int_least {
    static_assert(dgt <= 128);
    using type = first_enabled_t<std::enable_if<dgt <= 8, __int8_t>,
                                 std::enable_if<dgt <= 16, __int16_t>,
                                 std::enable_if<dgt <= 32, __int32_t>,
                                 std::enable_if<dgt <= 64, __int64_t>,
                                 std::enable_if<dgt <= 128, __int128_t> >;
};
template <int dgt> struct uint_least {
    static_assert(dgt <= 128);
    using type = first_enabled_t<std::enable_if<dgt <= 8, __uint8_t>,
                                 std::enable_if<dgt <= 16, __uint16_t>,
                                 std::enable_if<dgt <= 32, __uint32_t>,
                                 std::enable_if<dgt <= 64, __uint64_t>,
                                 std::enable_if<dgt <= 128, __uint128_t> >;
};

template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;

template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;

template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;

struct modint_base {};
template <typename T> using is_modint = std::is_base_of<modint_base, T>;
template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;


// is_integral
template <typename T>
using is_integral_t =
    std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||
                   std::is_same_v<T, __uint128_t>>;
};  // namespace internal
};  // namespace kyopro
#line 6 "library/src/stream.hpp"

namespace kyopro {
// read
void single_read(char& c) {
    c = getchar_unlocked();
    while (isspace(c)) c = getchar_unlocked();
}
template <typename T, internal::is_integral_t<T>* = nullptr>
void single_read(T& a) {
    a = 0;
    bool is_negative = false;
    char c = getchar_unlocked();
    while (isspace(c)) {
        c = getchar_unlocked();
    }
    if (c == '-') is_negative = true, c = getchar_unlocked();
    while (isdigit(c)) {
        a = 10 * a + (c - '0');
        c = getchar_unlocked();
    }
    if (is_negative) a *= -1;
}
template <typename T, internal::is_modint_t<T>* = nullptr>
void single_read(T& a) {
    long long x;
    single_read(x);
    a = T(x);
}
void single_read(std::string& str) {
    char c = getchar_unlocked();
    while (isspace(c)) c = getchar_unlocked();
    while (!isspace(c)) {
        str += c;
        c = getchar_unlocked();
    }
}
template<typename T>
void read(T& x) {single_read(x);}
template <typename Head, typename... Tail>
void read(Head& head, Tail&... tail) {
    single_read(head), read(tail...);
}

// write
void single_write(char c) { putchar_unlocked(c); }
template <typename T, internal::is_integral_t<T>* = nullptr>
void single_write(T a) {
    if (!a) {
        putchar_unlocked('0');
        return;
    }
    if (a < 0) putchar_unlocked('-'), a *= -1;
    char s[37];
    int now = 37;
    while (a) {
        s[--now] = (char)'0' + a % 10;
        a /= 10;
    }
    while (now < 37) putchar_unlocked(s[now++]);
}
template <typename T, internal::is_modint_t<T>* = nullptr>
void single_write(T a) {
    single_write(a.val());
}

void single_write(const std::string& str) {
    for (auto c : str) {
        putchar_unlocked(c);
    }
}

template<typename T>
void write(T x) { single_write(x); }
template <typename Head, typename... Tail> void write(Head head, Tail... tail) {
    single_write(head);
    putchar_unlocked(' ');
    write(tail...);
}
template <typename... Args> void put(Args... x) {
    write(x...);
    putchar_unlocked('\n');
}
};  // namespace kyopro

/**
 * @brief fastIO
 */
#line 2 "library/src/template.hpp"
#include <bits/stdc++.h>
#define rep(i, N) for (int i = 0; i < (N); i++)
#define all(x) std::begin(x), std::end(x)
#define popcount(x) __builtin_popcountll(x)
using i128 = __int128_t;
using ll = long long;
using ld = long double;
using graph = std::vector<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infl = std::numeric_limits<ll>::max() / 2;
constexpr ld eps = 1e-12;
const long double pi = acosl(-1);
constexpr uint64_t MOD = 1e9 + 7;
constexpr uint64_t MOD2 = 998244353;
constexpr int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1, 0};
constexpr int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1, 0};
template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) {
    return a > b && (a = b, true);
}
#line 3 "a.cpp"

using namespace std;
using namespace kyopro;

int main() {
    int n, k;
    read(n, k);

    set<int> a, b;
    {
        int m;
        read(m);
        rep(i, m) {
            int v;
            read(v);
            a.emplace(v);
        }
    }
    {
        int m;
        read(m);
        rep(i, m) {
            int v;
            read(v);
            b.emplace(v);
        }
    }

    vector<array<bool, 2>> dp(n + 1, array<bool, 2>{false, false});
    dp[0][0] = 1, dp[0][1] = 1;
    rep(i, n + 1) rep(j, 2) {
        if (b.count(i)) dp[i][0] = true;
        if (a.count(i)) dp[i][0] = false;
        if (i < n) dp[i + 1][j] |= dp[i][j];
        if (i + k <= n) dp[i + k][j] |= dp[i][j];
    }


    put(dp[n][0] ? "Yes" : "No");
}

yukicoder

結果

テストケース

ソースコード