setfunc/maxmin_partition.hpp

• View this file on GitHub
• Last update: 2026-08-19 06:34:57+09:00
• Include: #include "setfunc/maxmin_partition.hpp"
• Link: https://codeforces.com/blog/entry/153948?#comment-1367191

Depends on

• other/bit.hpp

Code

#include "other/bit.hpp"

// https://codeforces.com/blog/entry/153948?#comment-1367191
// O(n 2^n)
template <typename WT>
WT maxmin_partition(int K, vc<WT> A) {
  int N = len(A);
  if (N < K) return 0;
  assert(1 <= K && K <= N);
  vc<WT> S(1 << N);
  FOR(i, N) FOR(s, 1 << i) S[s | 1 << i] = S[s] + A[i];

  WT ANS = 0;
  int full = full_mask(N);
  using P = pair<int, WT>;
  vc<P> dp(1 << N);
  for (int s = 0; s < (1 << N); ++s) {
    int other = full ^ s;
    auto [k, w] = dp[s];
    WT W = S[other] + w;
    if (k == K - 1) {
      chmax(ANS, W);
      continue;
    }
    while (other) {
      int i = lowbit(other);
      other &= other - 1;
      int t = s | 1 << i;
      WT x = w + A[i];
      P nxt = (x * (K - k) >= W ? P(k + 1, 0) : P(k, x));
      chmax(dp[t], nxt);
    }
  }
  return ANS;
}

#line 1 "other/bit.hpp"

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  UINT s;
  all_bit(UINT s) : s(s) {}
  struct iter {
    UINT s;
    int operator*() const { return lowbit(s); }
    void operator++() { s &= s - 1; }
    bool operator!=(nullptr_t) const { return s; }
  };
  iter begin() const { return {s}; }
  nullptr_t end() const { return nullptr; }
};

template <typename UINT>
struct all_subset {
  UINT s;
  all_subset(UINT s) : s(s) {}
  struct iter {
    UINT s, t;
    bool done = false;
    UINT operator*() const { return t; }
    void operator++() {
      done = (t == 0);
      t = (t - 1) & s;
    }
    bool operator!=(nullptr_t) const { return !done; }
  };
  iter begin() const { return {s, s}; }
  nullptr_t end() const { return nullptr; }
};

constexpr u64 full_mask(int n) { return n == 64 ? -1ULL : (1ULL << n) - 1; }

u64 bit_reverse(u64 x) {
  x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL);
  x = ((x & 0x3333333333333333ULL) << 2) | ((x >> 2) & 0x3333333333333333ULL);
  x = ((x & 0x0f0f0f0f0f0f0f0fULL) << 4) | ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL);
  x = ((x & 0x00ff00ff00ff00ffULL) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffULL);
  x = ((x & 0x0000ffff0000ffffULL) << 16) | ((x >> 16) & 0x0000ffff0000ffffULL);
  x = (x << 32) | (x >> 32);
  return x;
}
#line 2 "setfunc/maxmin_partition.hpp"

// https://codeforces.com/blog/entry/153948?#comment-1367191
// O(n 2^n)
template <typename WT>
WT maxmin_partition(int K, vc<WT> A) {
  int N = len(A);
  if (N < K) return 0;
  assert(1 <= K && K <= N);
  vc<WT> S(1 << N);
  FOR(i, N) FOR(s, 1 << i) S[s | 1 << i] = S[s] + A[i];

  WT ANS = 0;
  int full = full_mask(N);
  using P = pair<int, WT>;
  vc<P> dp(1 << N);
  for (int s = 0; s < (1 << N); ++s) {
    int other = full ^ s;
    auto [k, w] = dp[s];
    WT W = S[other] + w;
    if (k == K - 1) {
      chmax(ANS, W);
      continue;
    }
    while (other) {
      int i = lowbit(other);
      other &= other - 1;
      int t = s | 1 << i;
      WT x = w + A[i];
      P nxt = (x * (K - k) >= W ? P(k + 1, 0) : P(k, x));
      chmax(dp[t], nxt);
    }
  }
  return ANS;
}

Back to top page