bzoj4123.cc

#include #include #include

using namespace std;

const int maxn = 1000003;

int n, l, a[maxn], b[maxn], s; int q[maxn], hd, tl;

int main() { #ifdef LAEKOV_LOCAL freopen(".in", “r”, stdin); #endif

scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
    scanf("%d", a + i);
for (int i = n + 1; i <= n * 2; ++ i)
    a[i] = a[i - n];
a[0] = 0;
for (int i = 1; i <= n * 2; ++ i)
    a[i] += a[i - 1];
l = (n + 1) >> 1;
for (int i = 1; i + l - 1 <= n * 2; ++ i)
    b[i] = a[i + l - 1] - a[i - 1];
s = 0;
hd = tl = 0;
for (int i = 1; i + l - 1 <= n * 2; ++ i) {
    while (hd < tl && b[q[tl - 1]] >= b[i])
        -- tl;
    q[tl ++] = i;
    while (hd < tl && q[hd] + l <= i)
        ++ hd;
    if (i >= l)
        s = max(s, b[q[hd]]);
}
printf("%d\n", s);

}