Submission #1062535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062535		awu	Uplifting Excursion (BOI22_vault)	C++14	20 / 100	925 ms	1340 KiB

vault

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
 
#define int long long
#define ll long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) [&](decltype(x) _x) {cerr << #x << " = " << _x << endl; return _x;}(x)
using pii =  pair<int, int>;
 
const ll inf = 1ll << 60;
// const int inf = 1 << 30;
 
template <typename T, typename U>
ostream& operator<<(ostream& out, pair<T, U> p) {
  return out << "(" << p.f << ", " << p.s << ")";
}
template <typename T, typename = decltype(begin(declval<T>()))>
typename enable_if<!is_same<T, string>::value, ostream&>::type operator<<(ostream& out, T x) {
  string dlm = "";
  out << "{";
  for(auto i : x) {
    out << dlm << i;
    dlm = ", ";
  }
  return out << "}";
}
 
const int K = 2;
const int K2 = 2;
const int K3 = 0;
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int m, l; cin >> m >> l;
  int* a = new int[2 * m + 1];
  a += m;
  int tot = 0;
  for(int i = -m; i <= m; i++) {
    cin >> a[i];
    tot += a[i];
    l -= a[i] * i;
  }
  l *= -1;
  if(l < 0) {
    // debug("HERE");
    l *= -1;
    reverse(a - m, a + m + 1);
  }
  // debug(l);
  int j = m;
  int ans = 0;
  while(l > m * m * K) {
    while(a[j] <= m * K3) {
      j--;
      if(j <= 0) {
        cout << "impossible" << endl;
        return 0;
      }
    }
    if(l - (a[j] - m * K3) * j > m * m * K) {
      l -= (a[j] - m * K3) * j;
      ans += (a[j] - m * K3);
      a[j] = 0;
    } else {
      int v = (l - m * m * K) / j;
      if(a[j] - v > m * K3) v++;
      l -= v * j;
      a[j] -= v;
      ans += v;
    }
  }
  vector<int> th;
  for(int i = -m; i <= m; i++) {
    if(i == 0) continue;
    for(int j = 0; j < min(a[i], m); j++) {
      th.push_back(i);
    }
  }
  random_shuffle(all(th));
  // debug(th);
  int* dp = new int[m * m * K * K2 * 2 + 1];
  dp += m * m * K * K2;
  fill(dp - m * m * K * K2, dp + m * m * K * K2 + 1, inf);
  dp[0] = 0;
  for(auto i : th) {
    if(i > 0) {
      for(int j = m * m * K * K2; j >= -m * m * K * K2; j--) {
        if(j - i >= -m * m * K * K2) {
          dp[j] = min(dp[j], dp[j - i] + 1);
        }
      }
    } else {
      for(int j = -m * m * K * K2; j <= m * m * K * K2; j++) {
        if(j - i <= m * m * K * K2) {
          dp[j] = min(dp[j], dp[j - i] + 1);
        }
      }
    }
  }
  if(dp[l] >= inf) {
    cout << "impossible" << endl;
    return 0;
  }
  cout << tot - (ans + dp[l]) << endl;
}

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