10782번: Hacker

https://www.acmicpc.net/problem/10782

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 5e5;
int a[MAX_N * 2], s[MAX_N * 2], dq[MAX_N][2], h, t, n, sz, res;
void push(int x, int y) {
    while (t - h && dq[t - 1][0] >= x) t--;
    dq[t][0] = x; dq[t++][1] = y;
    if (dq[h][1] <= y - sz) h++;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i <n; i++) scanf("%d", a + i);
    copy(a, a + n, a + n);
    for (int i = 1; i < 2 * n; i++) a[i] += a[i - 1];
    sz = (n + 1) / 2;
    for (int i = 0; i < n; i++) s[i] = a[i + sz] - a[i];
    copy(s, s + n, s + n);
    for (int i = 0; i < sz - 1; i++) push(s[i], i);
    for (int i = sz - 1; i < sz - 1 + n; i++) {
        push(s[i], i);
        res = max(res, dq[h][0]);
    }
    printf("%d", res);
    return 0;
}