时间复杂度是 $O(2 ^ {\frac{2}{n}} \times \frac{2}{n})$，但 T 完了

#include <bits/stdc++.h>
#define int long long
#define up(i, x, y) for(int i = x; i <= y; i ++ )
using namespace std;
const int N = 44;
int n, w, a[N], mx, m, p;
vector<int> u, v;
signed main() {
  cin >> w >> n;
  m = n >> 1, p = n - m;
  up(i, 1, n) cin >> a[i];
  up(i, 1, (1 << m) - 1) {
    int sum = 0;
    up(j, 1, m)
      if (i & (1 << (j - 1))) {
        sum += a[j];
        if (sum > w) {
          sum = 0;
          break;
        }
      }
    if (sum) u.push_back(sum);
  }
  up(i, 1, (1 << p) - 1) {
    int sum = 0;
    up(j, 1, p)
      if (i & (1 << j - 1)) {
        sum += a[j + m];
        if (sum > w) {
          sum = 0;
          break;
        }
      }
    if (sum) v.push_back(sum);
  }
  sort(u.begin(), u.end());
  sort(v.begin(), v.end());
  for (auto i : u) mx = max(mx, i);
  for (auto i : v) mx = max(mx, i);
  for (auto i : u) {
    int l = 0, r = v.size() - 1;
    while (l < r) {
      int mid = l + r >> 1;
      if (v[mid] + i > w) r = mid - 1;
      else l = mid;
    }
    mx = max(mx, i + v[l]);
  }
  cout << mx;
}