Submission #961873

#	Time	Username	Problem	Language	Result	Execution time	Memory
961873		garamlee500	Hacker (BOI15_hac)	C++17	100 / 100	180 ms	41760 KiB

hac

#include <iostream>

using namespace std;
int nums[500000];
//int sums[500000];
// 0 to 8388606 for root/internal
// 8388607 + x for leaves
int sums[16777215];
int n, k;

int getItem(int i){
    return nums[i%n];
}
int query(int l, int r, int i = 0, int x = 0, int y =8388607){
    if (l==x&&y==r){
        return sums[i];
    }

    int result= 1000000001;
    int mid = (x+y+1)/2;
    if (l < mid){
        result = min (result, query(l, min(r, mid-1), 2*i+1, x, mid-1));
    }
    if (r >= mid){
        result = min(result, query(max(l, mid), r, 2*i+2, mid, y));
    }
    return result;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> nums[i];
    }
    // Bytesar gets worst set of adjacent n/2 + n%2
    k = n/2 + n%2;
    sums[0+8388607]=0;
    // sums starting at i, up to i + k-1
    for (int i = 0; i < k; i++){
        sums[0+8388607] += nums[i];
    }
    for (int i = 1; i < n; i++){
        sums[i+8388607] = sums[i-1+8388607];
        sums[i+8388607] += getItem(i+k-1) - getItem(i-1);
        //cout << sums[i+8388607] << endl;
    }
    for (int i = 8388606; i>=0; i--){
        sums[i] = min(sums[2*i+1], sums[2*i+2]);
    }
    int best = 0;
    for (int i = 0; i < n; i++){
        // starts can be anywher from i-k+1, to i;
        int start = i-k+1;
        int last= i, minimum;
        if (start < 0){
            minimum = min(

                    query((start+n)%n, n-1),
                    query(0, last)

                    );
        }
        else{
            minimum = query(start, last);
        }
        best = max(best, minimum);
    }
    cout << best << '\n';
}

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