제출 #1359086

#제출 시각아이디문제언어결과실행 시간메모리
1359086iamhereforfunHacker (BOI15_hac)C++20
100 / 100
28 ms10332 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))
#define int long long

const int N = 5e5 + 5;
const int M = 15e5;
const int B = 18;
const long long K = 2;
const int LG = 60;
const long long INF = 1e18 + 5;
const int C = 26;
const int MOD = 1e9 + 7;

int n, a[N], l;
long long sum[N], cur, ans;
deque<int> dq;

void add(int i)
{
    while (!dq.empty())
    {
        if (sum[i] < sum[dq.back()])
        {
            dq.pop_back();
        }
        else
        {
            break;
        }
    }
    dq.push_back(i);
}

inline void solve()
{
    cin >> n;
    for (int x = 0; x < n; x++)
    {
        cin >> a[x];
    }
    l = (n + 1) / 2;
    cur = 0;
    for (int x = 0; x < l; x++)
    {
        cur += a[x];
    }
    sum[0] = cur;
    for (int x = 1; x < n; x++)
    {
        cur -= a[x - 1];
        cur += a[(x + l - 1 + n) % n];
        sum[x] = cur;
    }
    for (int x = (0 - l + 1 + n) % n; x < n; x++)
    {
        add(x);
    }
    ans = 0;
    add(0);
    ans = max(ans, sum[dq.front()]);
    for (int x = 1; x < n; x++)
    {
        // cout << x << " " << (x - l + n) % n << "\n";
        if (dq.front() == (x - l + n) % n)
        {
            dq.pop_front();
        }
        add(x);
        ans = max(ans, sum[dq.front()]);
    }
    cout << ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…