Submission #1355621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355621		ramzialoulou	Uplifting Excursion (BOI22_vault)	C++20	0 / 100	5093 ms	24388 KiB

vault

#include <bits/stdc++.h>

using namespace std;

const int N = 50509;
int dp[209][2 * N];

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];
  }
  for (int i = -m; i <= m; i++) {
    for (int x = -N; x <= N; x++) {
      dp[i + m][x + N] = -1;
    }
  }
  dp[0][N] = 0;
  for (int i = -m; i <= m; i++) {
    for (int x = -N; x <= N; x++) {
      if (dp[i + m][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;
          dp[i + 1 + m][k] = max(dp[i + 1 + m][k], dp[i + m][x + N] + j);
        }
      }
    }
  }
  L += N;
  if (0 <= L && L < 2 * N) {
    if (dp[2 * m + 1][L] == -1) {
      cout << "impossible" << '\n';
    } else {
      cout << dp[2 * m + 1][L] << '\n';
    }
  } else {
    cout << "impossible" << '\n';
  }
  return 0;
}

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:27:26: warning: iteration 101018 invokes undefined behavior [-Waggressive-loop-optimizations]
   27 |       if (dp[i + m][x + N] == -1) continue;
      |           ~~~~~~~~~~~~~~~^
vault.cpp:26:24: note: within this loop
   26 |     for (int x = -N; x <= N; x++) {
      |                      ~~^~~~
vault.cpp:21:24: warning: iteration 101018 invokes undefined behavior [-Waggressive-loop-optimizations]
   21 |       dp[i + m][x + N] = -1;
      |       ~~~~~~~~~~~~~~~~~^~~~
vault.cpp:20:24: note: within this loop
   20 |     for (int x = -N; x <= N; x++) {
      |                      ~~^~~~

• 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