Submission #491447

#	Time	Username	Problem	Language	Result	Execution time	Memory
491447		Rainbowbunny	Hacker (BOI15_hac)	C++17	100 / 100	62 ms	21644 KiB

hac

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

const int MAXN = 5e5 + 5;

int n;
long long pref[3 * MAXN], A[MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> A[i];
        pref[i] = pref[i - 1] + A[i];
    }
    int hh = (n + 1) / 2;
    for(int i = n + 1; i <= 2 * n; i++)
    {
        pref[i] = pref[i - 1] + A[i - n];
    }
    for(int i = 2 * n + 1; i <= 3 * n; i++)
    {
        pref[i] = pref[i - 1] + A[i - 2 * n];
    }
    long long ans = 0;
    deque <pair <long long, int> > Pos;
    for(int i = 1; i <= 2 * n; i++)
    {
        while(!Pos.empty() and Pos.front().second < i - hh + 1)
        {
            Pos.pop_front();
        }
        while(!Pos.empty() and Pos.back().first >= pref[i + hh - 1] - pref[i - 1])
        {
            Pos.pop_back();
        }
        Pos.push_back(make_pair(pref[i + hh - 1] - pref[i - 1], i));
        if(i >= hh)
        {
            ans = max(ans, Pos.front().first);
        }
    }
    cout << ans << '\n';
}

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