Submission #1229903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229903		avighna	Uplifting Excursion (BOI22_vault)	C++20	20 / 100	2416 ms	11848 KiB

vault

#include <bits/stdc++.h>

int main() {
  int m;
  int64_t l;
  std::cin >> m >> l;
  std::vector<std::pair<int64_t, int>> a;
  int64_t high = 0, low = 0;
  for (int64_t i = -m; i <= m; ++i) {
    uint64_t x;
    std::cin >> x;
    if (i > 0) {
      high += x * i;
    } else {
      low += x * i;
    }
    while (x > 0) {
      int w = std::bit_width(x) - 1;
      if (std::has_single_bit(x + 1)) {
        w += 1;
      }
      for (int bt = 0; bt < w; ++bt) {
        a.push_back({i << bt, 1LL << bt});
      }
      x -= (1LL << w) - 1;
    }
  }
  if (l < low or l > high) {
    std::cout << "impossible\n";
    return 0;
  }
  const int inf = 1e9;
  std::vector dp(2, std::vector<int>(high - low + 1, -inf));
  dp[0][-low] = 0;
  for (int i = 1; i <= a.size(); ++i) {
    for (int j = low; j <= high; ++j) {
      dp[i & 1][j - low] = dp[!(i & 1)][j - low];
      if (low <= j - a[i - 1].first and j - a[i - 1].first <= high) {
        dp[i & 1][j - low] = std::max(dp[i & 1][j - low], dp[!(i & 1)][j - a[i - 1].first - low] + a[i - 1].second);
      }
    }
  }
  int ans = dp[a.size() & 1][l - low];
  if (ans < 0) {
    std::cout << "impossible\n";
  } else {
    std::cout << ans << '\n';
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3-1: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10