#1032286 (C++23) No.733 分身並列コーディング

提出ソース

結果

問題	No.733 分身並列コーディング
ユーザー	cutmdo
提出日時	2024-12-19 16:36:48
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	232 ms / 1,500 ms
コード長	8,423 bytes
コンパイル時間	1,468 ms
コンパイル使用メモリ	100,148 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-12-19 16:36:55
合計ジャッジ時間	7,500 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	200 ms 6,820 KB
testcase_04	AC	195 ms 6,816 KB
testcase_05	AC	196 ms 6,820 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	205 ms 6,816 KB
testcase_08	AC	199 ms 6,820 KB
testcase_09	AC	68 ms 6,820 KB
testcase_10	AC	5 ms 6,816 KB
testcase_11	AC	5 ms 6,820 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	AC	24 ms 6,816 KB
testcase_15	AC	3 ms 6,816 KB
testcase_16	AC	2 ms 6,816 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	5 ms 6,816 KB
testcase_19	AC	67 ms 6,820 KB
testcase_20	AC	69 ms 6,820 KB
testcase_21	AC	24 ms 6,820 KB
testcase_22	AC	196 ms 6,820 KB
testcase_23	AC	24 ms 6,820 KB
testcase_24	AC	24 ms 6,816 KB
testcase_25	AC	2 ms 6,820 KB
testcase_26	AC	2 ms 6,816 KB
testcase_27	AC	3 ms 6,820 KB
testcase_28	AC	199 ms 6,820 KB
testcase_29	AC	200 ms 6,816 KB
testcase_30	AC	196 ms 6,820 KB
testcase_31	AC	227 ms 6,820 KB
testcase_32	AC	9 ms 6,820 KB
testcase_33	AC	10 ms 6,816 KB
testcase_34	AC	10 ms 6,816 KB
testcase_35	AC	10 ms 6,816 KB
testcase_36	AC	10 ms 6,816 KB
testcase_37	AC	9 ms 6,816 KB
testcase_38	AC	197 ms 6,820 KB
testcase_39	AC	198 ms 6,816 KB
testcase_40	AC	199 ms 6,816 KB
testcase_41	AC	9 ms 6,816 KB
testcase_42	AC	9 ms 6,820 KB
testcase_43	AC	10 ms 6,816 KB
testcase_44	AC	202 ms 6,820 KB
testcase_45	AC	199 ms 6,820 KB
testcase_46	AC	198 ms 6,816 KB
testcase_47	AC	200 ms 6,816 KB
testcase_48	AC	232 ms 6,820 KB

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

ソースコード

raw source code

#define PROBLEM "https://yukicoder.me/problems/no/733"

#include <iostream>
#include <vector>

#include <vector>
#include <ranges>
namespace mtd {  constexpr unsigned clz(unsigned int x) {    int c = 0;    if (x == 0) { return 0; }    if (x & 0xffff0000) {      x &= 0xffff0000;      c |= 0x10;    }    if (x & 0xff00ff00) {      x &= 0xff00ff00;      c |= 0x08;    }    if (x & 0xf0f0f0f0) {      x &= 0xf0f0f0f0;      c |= 0x04;    }    if (x & 0xcccccccc) {      x &= 0xcccccccc;      c |= 0x02;    }    if (x & 0xaaaaaaaa) { c |= 0x01; }    return c + 1;  }  constexpr unsigned ctz(unsigned int n) {    if (!n) return -1;    unsigned int c = 32;    n &= -static_cast<signed int>(n);    if (n) c--;    if (n & 0x0000FFFF) c -= 16;    if (n & 0x00FF00FF) c -= 8;    if (n & 0x0F0F0F0F) c -= 4;    if (n & 0x33333333) c -= 2;    if (n & 0x55555555) c -= 1;    return c;  }  constexpr unsigned long long popcount(unsigned long long x) {    x = x - ((x >> 1) & 0x5555555555555555);    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;    x = x + (x >> 8);    x = x + (x >> 16);    x = x + (x >> 32);    return x & 0x0000007f;  }}  
namespace mtd {  template <class T, class S>  inline auto chmax(T& t, const S& s) {    if (s > t) {      t = s;      return true;    }    return false;  }  template <class T, class S>  inline auto chmin(T& t, const S& s) {    if (s < t) {      t = s;      return true;    }    return false;  }  template <class S>  constexpr auto vec(S x) {    return x;  }  template <class S, class... T>  constexpr auto vec(S x, int n, T... ns) {    return std::vector(n, vec(x, ns...));  }}  
namespace mtd {  namespace ranges {    struct bit_index_view : public std::ranges::view_interface<bit_index_view> {      class iterator {        int i;        int bit;      public:        using difference_type = int;        using value_type = int;        using iterator_concept = std::forward_iterator_tag;        constexpr iterator() = default;        constexpr explicit iterator(int bit) : i(ctz(bit)), bit(bit) {}        constexpr auto operator*() const { return i; }        constexpr auto &operator++() {          bit ^= (1 << i);          i = ctz(bit);          return *this;        }        constexpr auto operator++(int) { return ++*this; }        constexpr auto operator==(const iterator &other) const {          return bit == other.bit;        }      };      int bit;      constexpr explicit bit_index_view(int bit) : bit(bit) {}      constexpr auto begin() const { return iterator(bit); }      constexpr auto end() const { return iterator(); }    };    struct bit_subset_view        : public std::ranges::view_interface<bit_subset_view> {      class iterator {        int i;        int bit;      public:        using difference_type = int;        using value_type = int;        using iterator_concept = std::bidirectional_iterator_tag;        constexpr iterator() = default;        constexpr explicit iterator(int bit) : i(bit), bit(bit) {}        constexpr auto operator*() const { return i; }        constexpr auto &operator++() {          i = (i - 1) & bit;          return *this;        }        constexpr auto operator++(int) { return ++*this; }        constexpr auto operator==(const iterator &other) const {          return i == other.i;        }      };      int bit;      constexpr explicit bit_subset_view(int bit) : bit(bit) {}      constexpr auto begin() const { return iterator(bit); }      constexpr auto end() const { return iterator(); }    };    struct bit_supset_view        : public std::ranges::view_interface<bit_supset_view> {      class iterator {        int i;        int bit;        int n;      public:        using difference_type = int;        using value_type = int;        using iterator_concept = std::bidirectional_iterator_tag;        constexpr iterator() = default;        constexpr explicit iterator(int bit, int n) : i(bit), bit(bit), n(n) {}        constexpr auto operator*() const { return i; }        constexpr auto &operator++() {          i = (i + 1) | bit;          return *this;        }        constexpr auto operator++(int) { return ++*this; }        constexpr auto operator==(const iterator &other) const {          return i == other.i && bit == other.bit && n == other.n;        }        constexpr auto operator==(            const std::default_sentinel_t &sentinel) const {          return i >= (1 << n);        }      };      int bit;      int n;      constexpr explicit bit_supset_view(int bit, int n) : bit(bit), n(n) {}      constexpr auto begin() const { return iterator(bit, n); }      constexpr auto end() const { return std::default_sentinel; }    };    struct k_bit_subset_view        : public std::ranges::view_interface<k_bit_subset_view> {      class iterator {        int i;        int n;      public:        using difference_type = int;        using value_type = int;        using iterator_concept = std::bidirectional_iterator_tag;        constexpr iterator() = default;        constexpr explicit iterator(int n, int k) : i((1 << k) - 1), n(n) {}        constexpr auto operator*() const { return i; }        constexpr auto &operator++() {          int x = i & -i;          int y = i + x;          i = (((i & ~y) / x) >> 1) | y;          return *this;        }        constexpr auto operator++(int) { return ++*this; }        constexpr auto operator==(const iterator &other) const {          return i == other.i && n == other.n;        }        constexpr auto operator==(            const std::default_sentinel_t &sentinel) const {          return i >= (1 << n);        }      };      int n, k;      constexpr explicit k_bit_subset_view(int n, int k) : n(n), k(k) {}      constexpr auto begin() const { return iterator(n, k); }      constexpr auto end() const { return std::default_sentinel; }    };  }    namespace views {    namespace __detail {      template <typename... _Args>      concept __can_bit_index_view = requires {        ranges::bit_index_view(std::declval<_Args>()...);      };      template <typename... _Args>      concept __can_bit_subset_view = requires {        ranges::bit_subset_view(std::declval<_Args>()...);      };      template <typename... _Args>      concept __can_bit_supset_view = requires {        ranges::bit_supset_view(std::declval<_Args>()...);      };      template <typename... _Args>      concept __can_k_bit_subset_view = requires {        ranges::k_bit_subset_view(std::declval<_Args>()...);      };    }      struct _BitIndex {      template <class... _Tp>      requires __detail::__can_bit_index_view<_Tp...>      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {        return ranges::bit_index_view(std::forward<_Tp>(__e)...);      }    };    inline constexpr _BitIndex bit_index{};    struct _BitSubsetView {      template <class... _Tp>      requires __detail::__can_bit_subset_view<_Tp...>      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {        return ranges::bit_subset_view(std::forward<_Tp>(__e)...);      }    };    inline constexpr _BitSubsetView bit_subset{};    struct _BitSupsetView {      template <class... _Tp>      requires __detail::__can_bit_supset_view<_Tp...>      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {        return ranges::bit_supset_view(std::forward<_Tp>(__e)...);      }    };    inline constexpr _BitSupsetView bit_supset{};    struct _KBitSubsetView {      template <class... _Tp>      requires __detail::__can_k_bit_subset_view<_Tp...>      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {        return ranges::k_bit_subset_view(std::forward<_Tp>(__e)...);      }    };    inline constexpr _KBitSubsetView k_bit_subset{};  }  }  

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int t, n;
  std::cin >> t >> n;
  std::vector<int> a(n);
  for (auto i : std::views::iota(0, n)) { std::cin >> a[i]; }

  auto sum = mtd::vec(0, 1 << n);
  for (auto bit : std::views::iota(1, 1 << n)) {
    auto b = mtd::ctz(bit);
    sum[bit] = (bit == (1 << b) ? 0 : sum[bit ^ (1 << b)]) + a[b];
  }

  auto dp = mtd::vec(n, 1 << n);
  for (auto bit : std::views::iota(0, 1 << n)) {
    if (sum[bit] <= t) { dp[bit] = 1; }
  }
  for (auto bit : std::views::iota(0, 1 << n)) {
    for (auto sub : mtd::views::bit_subset(bit)) {
      mtd::chmin(dp[bit], dp[sub] + dp[bit ^ sub]);
    }
  }
  std::cout << dp[(1 << n) - 1] << std::endl;
}