Submission #209977

#	Time	Username	Problem	Language	Result	Execution time	Memory
209977		IOrtroiii	Candies (JOI18_candies)	C++14	100 / 100	1499 ms	15624 KiB

candies

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using State = array<array<vector<ll>, 2>, 2>;

vector<ll> merge(const vector<ll> &lf, const vector<ll> &rg) {
   if (lf.empty()) return rg;
   if (rg.empty()) return lf;
   deque<ll> lfd;
   deque<ll> rgd;
   for (int i = 0; i + 1 < int(lf.size()); ++i) {
      lfd.emplace_back(lf[i + 1] - lf[i]);
   }
   for (int i = 0; i + 1 < int(rg.size()); ++i) {
      rgd.emplace_back(rg[i + 1] - rg[i]);
   }
   vector<ll> ans = {lf[0] + rg[0]};
   while (lfd.size() && rgd.size()) {
      if (lfd.front() > rgd.front()) {
         ans.emplace_back(ans.back() + lfd.front());
         lfd.pop_front();
      } else {
         ans.emplace_back(ans.back() + rgd.front());
         rgd.pop_front();
      }
   }
   while (lfd.size()) {
      ans.emplace_back(ans.back() + lfd.front());
      lfd.pop_front();
   }
   while (rgd.size()) {
      ans.emplace_back(ans.back() + rgd.front());
      rgd.pop_front();
   }
   return ans;
}

void optimize(vector<ll> &x, const vector<ll> &y) {
   while (x.size() < y.size()) {
      x.emplace_back(0ll);
   }
   for (int i = 0; i < int(y.size()); ++i) {
      x[i] = max(x[i], y[i]);
   }
}

State merge(const State &lf, const State &rg) {
   State ans = {};
   for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
         for (int k = 0; k < 2; ++k) {
            for (int l = 0; l < 2; ++l) {
               if (!j || !k) {
                  optimize(ans[i][l], merge(lf[i][j], rg[k][l]));
               }
            }
         }
      }
   }
   return ans;
}

void modify(State &s) {
   for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
         if (i) optimize(s[i][j], s[i - 1][j]);
         if (j) optimize(s[i][j], s[i][j - 1]);
      }
   }
}

int main() {
   ios_base::sync_with_stdio(false);
   int N;
   cin >> N;
   vector<ll> A(N);
   for (int i = 0; i < N; ++i) cin >> A[i];
   function<State(int, int)> solve = [&](int l, int r) {
      State ans = {};
      if (l == r) {
         ans[0][0] = {0};
         ans[1][1] = {0, A[l]};
      } else {
         int md = (l + r) >> 1;
         ans = merge(solve(l, md), solve(md + 1, r));
      }
      modify(ans);
      return ans;
   };
   auto ans = solve(0, N - 1);
   for (int i = 1; i <= (N + 1) / 2; ++i) cout << ans[1][1][i] << "\n";
   return 0;
}

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