Dynamic Programming with Bitmasks - CSES Elevator Rides

elevator.cpp

#include <bits/stdc++.h>
using namespace std;

int getMinTrips(int n, int x, vector<int> w) {
  int limit = 1 << n;
  vector<pair<int,int>> dp(limit, {n + 1, 0});
  dp[0] = {1, 0};

  for (int s=1; s < limit; s++) {
    for (int person=0; person < n; person++) {
      if (s & (1 << person)) {
        pair<int, int> optimum = dp[s ^ (1 << person)];

        if (optimum.second + w[person] <= x) {
          optimum.second += w[person];
        }
        else {
          optimum.first += 1;
          optimum.second = w[person];
        }

        dp[s] = min(dp[s], optimum);
      }
    }
  }

  return dp[limit - 1].first;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, x;
  vector<int> w;
  cin >> n >> x;
  w.resize((1 << n) + 1);
  for (auto &val : w) cin >> val;
  cout << getMinTrips(n, x, w) << endl;
  return 0;
}