Submission #823329

#	Time	Username	Problem	Language	Result	Execution time	Memory
823329		serifefedartar	Hacker (BOI15_hac)	C++17	100 / 100	168 ms	18816 KiB

hac

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000009
#define LOGN 20
#define MAXN 500005
#define int long long

int n;
int sg[4*MAXN];
vector<int> v, pref;
int get_sum(int begin, int len) {
    if (begin + len - 1 <= n)
        return pref[begin + len - 1] - pref[begin - 1];
    else
        return pref[n] - pref[begin - 1] + pref[len - n + begin - 1];
}

void init(int k, int a, int b) {
    if (a == b) {
        sg[k] = get_sum(a, n/2);
        return ; 
    }
    init(2*k, a, (a+b)/2);
    init(2*k+1, (a+b)/2+1, b);
    sg[k] = max(sg[2*k], sg[2*k+1]);
}

int query(int k, int a, int b, int q_l, int q_r) {
    if (a > q_r || b < q_l)
        return 0;
    if (q_l <= a && b <= q_r)
        return sg[k];
    return max(query(2*k, a, (a+b)/2, q_l, q_r), query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}

signed main() {
    fast
    cin >> n;

    v = vector<int>(n+1);
    pref = vector<int>(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        pref[i] = pref[i-1] + v[i]; 
    }
    init(1, 1, n);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int max_protect;
        if (n % 2 && i + 1 + n/2 <= n)
            max_protect = query(1, 1, n, i + 1, i + 1 + n/2);
        else if (n % 2 == 0 && i + n/2 <= n)
            max_protect = query(1, 1, n, i + 1, i + n/2);
        else if (n % 2)
            max_protect = max(query(1, 1, n, i + 1, n), query(1, 1, n, 1, 1 + i + n/2 - n));
        else
            max_protect = max(query(1, 1, n, i + 1, n), query(1, 1, n, 1, i - n/2));
        ans = max(ans, pref[n] - max_protect);
    }
    cout << ans << "\n";
}

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