제출 #1166882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166882		fryingduc	Hacker (BOI15_hac)	C++20	100 / 100	243 ms	180544 KiB

hac

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e6 + 5;
const int LG = 20;
int n, a[maxn];
int lg2[maxn];
long long st[maxn][LG + 1];
long long pref[maxn];

long long get(int l, int r) {
  int p = lg2[r - l + 1];
  return min(st[l][p], st[r - (1 << p) + 1][p]);
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    a[i + n] = a[i];
  }
  int t = (n + 1) / 2;
  for (int i = 1; i <= n << 1; ++i) {
    pref[i] = pref[i - 1] + a[i];
    st[i][0] = (i < t ? -1 : pref[i] - pref[i - t]);
  }
  for (int j = 1; j <= LG; ++j) {
    for (int i = 1; i + (1 << j) <= (n << 1) + 1; ++i) {
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);;
    }
  }
  long long res = 0;
  for (int i = t; i <= n * 2 - t + 1; ++i) {
    res = max(res, get(i, i + t - 1));
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  for (int i = 2; i < maxn; ++i) {
    lg2[i] = lg2[i >> 1] + 1;
  }
  solve();

  return 0;
}

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