Submission #688034

#	Time	Username	Problem	Language	Result	Execution time	Memory
688034		bdl	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	13 ms	468 KiB

vault

#include <iostream>
using namespace std;

const int N = 300, B = N * N * 2;
const long long INF = 1e18;

namespace dq {
  pair<long long, int> d[B * 2 + 1];
  int u, v, l, r;
 
  void clear() {
    u = v = l = r = 0;
  }
  int size() {
    return v - u;
  }
  void push(long long x) {
    while (r - l > 0 && d[r - 1].first <= x)
      r--;
    d[r++] = {x, v++};
  }
  void pop() {
    if (d[l].second == u++)
      l++;
  }
  long long query() {
    return d[l].first;
  }
}

void process(long long *f, int b, int i, int c, int t) {
  if (i > 0) {
    for (int md = 0; md < i; md++) {
      dq::clear();
      for (int j = md; j <= b * 2; j += i) {
        dq::push(f[j] == -INF ? -INF : f[j] - j * t);
        if (dq::size() > c + 1)
          dq::pop();
        f[j] = dq::query() == -INF ? -INF : dq::query() + j * t;
      }
    }
  } else if (i < 0) {
    i = -i;
    for (int md = 0; md < i; md++) {
      dq::clear();
      for (int j = (b * 2 - md) / i * i + md; j >= 0; j -= i) {
        dq::push(f[j] == -INF ? -INF : f[j] + j * t);
        if (dq::size() > c + 1)
          dq::pop();
        f[j] = dq::query() == -INF ? -INF : dq::query() - j * t;
      }
    }
  } else if (t > 0) {
    for (int j = 0; j <= b * 2; j++)
      if (f[j] != -INF)
        f[j] += c * t;
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n;
  long long m;
  cin >> n >> m;
  static long long k[N * 2 + 1], u[N * 2 + 1];
  long long m_ = 0;
  for (int i = -n; i <= +n; i++) {
    cin >> k[n + i];
    u[n + i] = k[n + i], m_ += i * k[n + i];
  }
  if (m_ < m) {
    for (int i = n; i > 0 && m_ < m; i--) {
      long long t = min(u[n - i], (m - m_) / i);
      m_ += t * i, u[n - i] -= t;
    }
    if (m_ < m) {
      cout << "impossible\n";
      return 0;
    }
  } else if (m_ > m) {
    for (int i = n; i > 0 && m_ > m; i--) {
      long long t = min(u[n + i], (m_ - m) / i);
      m_ -= t * i, u[n + i] -= t;
    }
    if (m_ > m) {
      cout << "impossible\n";
      return 0;
    }
  }
  int b = n * n * 2;
  static long long f[B * 2 + 1];
  for (int i = -b; i <= +b; i++)
    f[b + i] = -INF;
  f[b + 0] = 0;
  for (int i = -n; i <= +n; i++) {
    process(f, b, -i, min(u[n + i], (long long) n * 2), -1);
    process(f, b, +i, min(k[n + i] - u[n + i], (long long) n * 2), +1);
  }
  if (f[b + m - m_] == -INF) {
    cout << "impossible\n";
    return 0;
  }
  long long ans = f[b + m - m_];
  for (int i = 0; i <= n * 2; i++)
    ans += u[i];
  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