Submission #1268013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268013		rtri	Hacker (BOI15_hac)	C++20	0 / 100	0 ms	324 KiB

hac

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> vals;

class ST {
  int n;
  vector<int> val;

public:
  ST(vector<int> _val) {
    val = _val;
    n = _val.size() / 2;
    for (int i = n - 1; i > 0; i--)
      val[i] = min(val[(i << 1)], val[1 | (i << 1)]);
  }
  int query(int l, int r) {
    if (n < r) {
      r -= n;
      return min(query(0, r), query(l, n));
    }

    int ans = 1e9;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        ans = min(ans, val[l++]);
      if (r & 1)
        ans = min(ans, val[--r]);
    }
    return ans;
  }
};

int main() {
  cin >> n;

  vals.resize(n);
  for (int i = 0; i < n; i++)
    cin >> vals[i];

  int rollsum = 0;
  int sz = (n + 1) / 2;
  for (int i = 0; i < sz; i++) {
    rollsum += vals[i];
  }

  vector<int> val(n * 2, 1e9);
  for (int i = 0; i < n; i++) {
    val[n + i] = rollsum;
    rollsum += vals[(i + n / 2) % n] - vals[i % n];
  }
  ST st(val);

  int ans = 0;
  for (int i = 0; i < n; i++) {
    int res = st.query(i, i + sz + 1);
    ans = max(res, ans);
  }

  cout << ans << endl;

  return 0;
}

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