제출 #1355646

#제출 시각아이디문제언어결과실행 시간메모리
1355646ramzialoulouUplifting Excursion (BOI22_vault)C++20
5 / 100
5095 ms9824 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = int(6e5) + 9;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int m;
  cin >> m;
  long long L;
  cin >> L;
  vector<int> a(2 * m + 1);
  for (int i = -m; i <= m; i++) {
    cin >> a[i + m];
  }
  vector<int> dp(2 * N + 1, -1), ndp(2 * N + 1, -1);
  dp[N] = 0;
  for (int i = -m; i <= m; i++) {
    for (int x = -N; x <= N; x++) {
      ndp[x + N] = -1;
    }
    for (int x = -N; x <= N; x++) {
      if (dp[x + N] == -1) continue;
      for (int j = 0; j <= a[i + m]; j++) {
        int k = x + i * j;
        if (-N <= k && k <= N) {
          k += N;
          ndp[k] = max(ndp[k], dp[x + N] + j);
        }
      }
    }
    swap(dp, ndp);
  }
  L += N;
  if (0 <= L && L <= 2 * N) {
    if (dp[L] == -1) {
      cout << "impossible" << '\n';
    } else {
      cout << dp[L] << '\n';
    }
  } else {
    cout << "impossible" << '\n';
  }
  return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…