Submission #1229426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229426		avighna	Uplifting Excursion (BOI22_vault)	C++20	0 / 100	825 ms	589824 KiB

vault

#include <bits/stdc++.h>

int main() {
  int m;
  int64_t l;
  std::cin >> m >> l;
  std::vector<int> a;
  int64_t high = 0, low = 0;
  for (int i = -m; i <= m; ++i) {
    int64_t x;
    std::cin >> x;
    for (int j = 0; j < x; ++j) {
      a.push_back(i);
      if (i > 0) { 
        high += i;
      } else {
        low += i;
      }
    }
  }
  if (l < low or l > high) {
    std::cout << "impossible\n";
    return 0;
  }
  const int inf = 1e9;
  std::vector dp(a.size() + 1, 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][j - low] = dp[i - 1][j - low];
      if (low <= j - a[i - 1] and j - a[i - 1] <= high) {
        dp[i][j - low] = std::max(dp[i][j - low], dp[i - 1][j - a[i - 1] - low] + 1);
      }
    }
  }
  int ans = dp[a.size()][l - low];
  if (ans < 0) {
    std::cout << "impossible\n";
  } else {
    std::cout << ans << '\n';
  }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 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