제출 #1268024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268024		rtri	Hacker (BOI15_hac)	C++20	100 / 100	147 ms	27776 KiB

hac

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

typedef long long int ll;

int n;
vector<ll> vals;

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

public:
  ST(vector<ll> _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)]);
  }
  ll query(int l, int r) {
    if (n < r && n < l)
      return query(l % n, r % n);
    else if (n < r)
      return min(query(0, r - n), query(l, n));

    ll ans = 1e15;
    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];

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

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

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

  cout << ans << endl;

  return 0;
}

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