Submission #642048

#	Time	Username	Problem	Language	Result	Execution time	Memory
642048		valerikk	Candies (JOI18_candies)	C++17	100 / 100	485 ms	16208 KiB

candies

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const ll INF = 2e18;

void upd(vector<ll> &a, const vector<ll> &b) {
  if (a.size() < b.size()) {
    a.resize(b.size(), -INF);
  }
  for (int i = 0; i < (int) b.size(); ++i) {
    a[i] = max(a[i], b[i]);
  }
}

void upd(vector<ll> &t, const vector<ll> &a, const vector<ll> &b) {
  int sz_a = a.size(), sz_b = b.size();

  int mn_a = 0;
  while (mn_a < sz_a && a[mn_a] == -INF) {
    ++mn_a;
  }
  
  if (mn_a == sz_a) return;

  int mx_a = mn_a;
  while (mx_a + 1 < sz_a && a[mx_a + 1] != -INF) {
    ++mx_a;
  } 

  int mn_b = 0;
  while (mn_b < sz_b && b[mn_b] == -INF) {
    ++mn_b;
  }
  
  if (mn_b == sz_b) return;

  int mx_b = mn_b;
  while (mx_b + 1 < sz_b && b[mx_b + 1] != -INF) {
    ++mx_b;
  }

  vector<ll> da, db;
  for (int i = mn_a + 1; i <= mx_a; ++i) {
    da.push_back(a[i] - a[i - 1]);
  }
  for (int i = mn_b + 1; i <= mx_b; ++i) {
    db.push_back(b[i] - b[i - 1]);
  }

  vector<ll> d(da.size() + db.size());
  merge(da.begin(), da.end(), db.begin(), db.end(), d.begin(), greater<ll>());

  vector<ll> c(mx_a + mx_b + 1, -INF);
  c[mn_a + mn_b] = a[mn_a] + b[mn_b];
  for (int i = 0; i < mx_a - mn_a + mx_b - mn_b; ++i) {
    c[mn_a + mn_b + i + 1] = c[mn_a + mn_b + i] + d[i];
  }

  if (t.size() < c.size()) {
    t.resize(c.size(), -INF);
  }
  for (int i = 0; i < (int) c.size(); ++i) {
    t[i] = max(t[i], c[i]);
  }
} 

const int N = 2e5 + 7;

typedef array<array<vector<ll>, 2>, 2> Res;

Res merge(const Res &a, const Res &b) {
  Res c;
  for (int al = 0; al < 2; ++al) {
    for (int ar = 0; ar < 2; ++ar) {
      for (int bl = 0; bl < 2 - ar; ++bl) {
        for (int br = 0; br < 2; ++br) {
          upd(c[al][br], a[al][ar], b[bl][br]);
        }
      }
    }
  }
  return c;
}

int n;
ll a[N];

Res solve(int l, int r) {
  if (r - l == 1) {
    Res res;
    res[0][0].resize(1, -INF);
    res[0][0][0] = 0;
    res[1][1].resize(2, -INF);
    res[1][1][1] = a[l];
    return res;
  }
  int mid = (l + r) / 2;
  return merge(solve(l, mid), solve(mid, r));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  auto res = solve(0, n);

  vector<ll> ans((n + 1) / 2 + 1, -INF);
  for (int l = 0; l < 2; ++l) {
    for (int r = 0; r < 2; ++r) {
      upd(ans, res[l][r]);
    }
  }

  for (int i = 1; i <= (n + 1) / 2; ++i) {
    cout << ans[i] << "\n";
  }
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92