Submission #600242

#	Time	Username	Problem	Language	Result	Execution time	Memory
600242		MilosMilutinovic	Hacker (BOI15_hac)	C++14	100 / 100	157 ms	86708 KiB

hac

/**
 *    author:  wxhtzdy
 *    created: 20.07.2022 16:47:00
**/
#include <bits/stdc++.h>

using namespace std;

// usage:
//   auto fun = [&](int i, int j) { return min(i, j); };
//   SparseTable<int, decltype(fun)> st(a, fun);
// or:
//   SparseTable<int> st(a, [&](int i, int j) { return min(i, j); });
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<long long> pref(2 * n + 1);
  for (int i = 0; i < 2 * n; i++) {
    pref[i + 1] = pref[i] + a[i % n];
  }
  int moves = (n + 1) / 2;   
  vector<long long> val(n + 1);
  for (int i = 1; i <= n; i++) {
    val[i] = pref[i + moves - 1] - pref[i - 1];
  }
  SparseTable<long long> st(val, [&](long long a, long long b) { return min(a, b); });
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    long long mn;
    if (i - moves >= 0) {
      mn = st.get(i - moves + 1, i);      
    } else {
      mn = min(st.get(1, i), st.get(n - (moves - i) + 1, n));
    }
    ans = max(ans, mn);     
  }
  cout << ans << '\n';                                                     
  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40