Submission #602632

#	Time	Username	Problem	Language	Result	Execution time	Memory
602632		veehz	Uplifting Excursion (BOI22_vault)	C++17	5 / 100	5064 ms	4180 KiB

vault

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

typedef long long ll;

ll negativeOne = -1;
ll m, l;
int maxi, mini;
vector<ll> a, x;

inline auto& get(int i) { return a[i + m]; }
inline auto& getx(int i) {
  if (i < mini || i > maxi) return negativeOne;
  return x[i - mini];
}

int main() {
  cin >> m >> l;
  ll ans = 0;
  a.resize(2 * m + 1);
  for (int i = 0; i < 2 * m + 1; i++) cin >> a[i];

  maxi = mini = 0;
  for (int i = 1; i <= m; i++) {
    maxi += get(i) * i;
    mini -= get(-i) * i;
  }


  x.assign(maxi - mini + 1, negativeOne);
  getx(0) = get(0);
  for (int i = 1; i <= m; i++) {
    for (int j = maxi; j >= mini; j--) {
      for (int k = 1; k <= get(i); k++) {
        if (getx(j - k * i) != negativeOne) {
          getx(j) = max(getx(j), getx(j - k * i) + k);
        }
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    for (int j = mini; j <= maxi; j++) {
      for (int k = 1; k <= get(-i); k++) {
        if (getx(j + k*i) != negativeOne) {
          getx(j) = max(getx(j), getx(j + k*i) + k);
        }
      }
    }
  }

  if(getx(l) != negativeOne) cout << getx(l) << endl;
  else cout << "impossible" << endl;
}

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:19:6: warning: unused variable 'ans' [-Wunused-variable]
   19 |   ll ans = 0;
      |      ^~~

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