Submission #230730

#	Time	Username	Problem	Language	Result	Execution time	Memory
230730		emil_physmath	Hacker (BOI15_hac)	C++17	100 / 100	375 ms	28640 KiB

hac

#include <iostream>
#include <limits>
#include <vector>
using namespace std;
 
int t[4000'000];
 
void Build(const vector<int>& a, int v, int vl, int vr)
{
    if (vl == vr)
    {
        t[v] = a[vr];
        return;
    }
    int vm = (vl + vr) / 2;
    Build(a, v * 2, vl, vm);
    Build(a, v * 2 + 1, vm + 1, vr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}
int Min(int v, int vl, int vr, int l, int r)
{
    if (vl > r || l > vr)
        return numeric_limits<int>::max();
    if (l <= vl && vr <= r)
        return t[v];
    int vm = (vl + vr) / 2;
    return min(Min(v * 2, vl, vm, l, r), Min(v * 2 + 1, vm + 1, vr, l, r));
}
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    vector<int> b(3 * n), pref(3 * n);
    for (int i = 0; i < 3 * n; ++i)
    {
        b[i] = a[i % n];
        pref[i] = (i ? pref[i - 1] : 0) + b[i];
    }
    vector<int> sum(2 * n);
    for (int i = 0; i < 2 * n; ++i)
        sum[i] = pref[i + (n + 1) / 2 - 1] - (i ? pref[i - 1] : 0);
    Build(sum, 1, 0, 2 * n - 1);
    int ans = 0;
    for (int i = n; i < 2 * n; ++i)
        ans = max(ans, Min(1, 0, 2 * n - 1, i - (n + 1) / 2 + 1, i));
    cout << ans;
}

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