제출 #1185791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185791		Rokas159	Hacker (BOI15_hac)	C++20	100 / 100	157 ms	31744 KiB

hac

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

#define int long long
#define endl '\n'

const int MAXN = 5e5+2;

int l[2*MAXN], r[2*MAXN], val[2*MAXN];
int sums[MAXN];

int n;

int currInd = 0;
void build(int v = 1) {
    if (v < n) {
        build(v*2);
        build(v*2+1);
        l[v] = l[v*2];
        r[v] = r[v*2+1];
        val[v] = min(val[v*2], val[v*2+1]);
    } else {
        l[v] = currInd;
        r[v] = currInd;
        val[v] = sums[currInd++];
    }
}

int query(int L, int R, int v = 1) {
    if (R < l[v] || r[v] < L) {
        return INT32_MAX;
    } else if (L <= l[v] && r[v] <= R) {
        return val[v];
    } else {
        return min(query(L, R, v*2), query(L, R, v*2+1));
    }
}

signed main() {
    cin.tie(nullptr); cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> n;

    int a[n];

    int sum = 0;
    int half = (n+1)/2;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i < half) {
            sum += a[i];
        }
    }


    for (int i = 0; i <= n; i++) {
        sums[i%n] = sum;

        sum += a[(i+half)%n];
        sum -= a[i%n];
    }

    build();

    int ans = 0;

    for (int i = 0; i < n; i++) {
        int L = (i-half+1  +n)%n;
        int R = i;

        if (R < L) {
            ans = max(ans, min(query(0, R), query(L, n-1)));
        } else {
            ans = max(ans, query(L, R));
        }
    }

    cout << ans << endl;

    cout.flush();
    return 0;
}

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