Submission #672657

#	Time	Username	Problem	Language	Result	Execution time	Memory
672657		finn__	Hacker (BOI15_hac)	C++17	100 / 100	122 ms	9916 KiB

hac

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

int main()
{
    size_t n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a)
        cin >> x;

    vector<int> p(n, 0);
    for (size_t i = 0; i < (n + 1) / 2; i++)
        p[0] += a[i];
    for (size_t i = 1; i < n; i++)
        p[i] = p[i - 1] + a[(i + (n + 1) / 2 - 1) % n] - a[i - 1];

    deque<pair<int, size_t>> q;

    for (size_t i = 0; i < (n + 1) / 2; i++)
    {
        while (!q.empty() && q.back().first >= p[i])
            q.pop_back();
        q.push_back({p[i], i});
    }
    int max_value = q.front().first;

    for (size_t i = 1; i < n; i++)
    {
        if (!q.empty() && q.front().second == i - 1)
            q.pop_front();
        while (!q.empty() && q.back().first >= p[(i + (n + 1) / 2 - 1) % n])
            q.pop_back();
        q.push_back({p[(i + (n + 1) / 2 - 1) % n], (i + (n + 1) / 2 - 1) % n});
        max_value = max(max_value, q.front().first);
    }

    cout << max_value << '\n';
}

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