Submission #634770

#	Time	Username	Problem	Language	Result	Execution time	Memory
634770		null_awe	Uplifting Excursion (BOI22_vault)	C++14	0 / 100	5089 ms	212 KiB

vault

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

#define ll long long

int main() {
  int n; cin >> n; n = 2 * n + 1;
  ll l; cin >> l;
  vector<ll> arr(n); for (int i = 0; i < n; ++i) cin >> arr[i];
  if (l < 0) reverse(arr.begin(), arr.end()), l = -l;
  for (int i = 0; i < n / 2; ++i) arr[n - 1 - i] += arr[i], l += (n / 2 - i) * arr[i], arr[i] = 0;
  ll sum = 0;
  vector<ll> count(n / 2 + 1); count[0] = arr[n / 2];
  for (int i = 1; i <= n / 2; ++i) {
    if (arr[i + n / 2] * i + sum <= l) sum += arr[i + n / 2] * i, swap(count[i], arr[i + n / 2]);
    else {
      int take = (l - sum) / i;
      sum += i * take, count[i] += take, arr[i + n / 2] -= take;
    }
  }
  while (sum < l) {
    ll diff = l - sum;
    vector<ll> narr, ncount;
    int mn = INT_MAX;
    ll nsum = -1;
    for (int i = 1; i <= n / 2; ++i) {
      if (!arr[i + n / 2]) continue;
      ll sum2 = 0, cnt = 0;
      vector<ll> carr = arr, ccount = count;
      for (int j = i - 1; j > 0; --j) {
        while (ccount[j]) {
          if (i - sum2 <= diff) break;
          sum2 += j, ++carr[j + n / 2], --ccount[j], ++cnt;
        }
        if (i - sum2 <= diff) break;
      }
      ++ccount[i];
      if (cnt >= mn || i - sum2 > diff) continue;
      narr = carr, ncount = ccount, mn = cnt, nsum = sum + i - sum2;
    }
    if (mn == INT_MAX) {
      cout << "impossible\n";
      return 0;
    }
    arr = narr, count = ncount, sum = nsum;
  }
  if (sum != l) cout << "impossible\n";
  else {
    ll ans = 0;
    for (ll num : count) ans += num;
    cout << ans << '\n';
  }
  return 0;
}

• 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