Автор, розробник, автор розбору: Iлля Пермяков

Помiтимо, що фактично в задачi потрiбно знайти мiнiмальну суму на двох вiдрiзках однакової довжини, таких що мiж ними є хоча б один елемент. Нехай ця сума дорiвнюватиме ~T~ , а сума усiх елементiв масиву p дорiвнюватиме ~S~. Тодi якщо ~T > 0~, то вiдповiддю буде ~S~, iнакше вiдповiддю буде ~S-T~ . Тепер залишилось навчитись знаходити суму ~T~.

Спочатку зафiксуємо x — довжину двох вiдрiзкiв. Тепер для кожного iндексу i ~(x ⩽ i ⩽ n-x + 1)~ порахуємо два значення:

• Мiнiмальна сума на вiдрiзку довжини x, найправiший елемент якого має iндекс ~⩽ i~. Позначимо її за ~A_{i,x}~.
• Мiнiмальна сума на вiдрiзку довжини x, лiвiший елемент якого має iндекс ~⩾ i~. Позначимо її за ~B_{i,x}~.

Цi значення можна порахувати, наприклад, за допомогою префiксних та суфiксних мiнiмумiв.

Тепер зафiксуємо iндекс y ~(x < y < n-x + 1)~ — це буде один з елементiв, що знаходиться мiж двома вiдрiзками. Помiтимо, що якщо у вiдповiдi ~y~ знаходиться мiж двома частинами завiси, то лiву частину оптимально буде розмiстити на такому вiдрiзку лiвiше ~y~, що має мiнiмальну суму. Аналогiчно розмiстимо праву завiсу. Сума елементiв при оптимальному розмiщеннi лiвої частини завiси буде дорiвнювати ~A_{y-1,x}~, а правої - ~B_{y+1,x}~. Отже, для фiксованого ~y~ та фiксованого ~x~, сума ~T~ дорiвнюватиме ~A_{y-1,x} + B_{y+1,x}~. Тепер залишилось перебрати ~x~ та ~y~, i серед усiх таких варiантiв обрати мiнiмальний.

Сумарний час роботи рiшення - ~O(n^2)~.

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3+69;
int A[N];
int64_t suf[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> A[i];
    int64_t res = 0;
    for (int x = 1; x <= n/2; ++x) {
        int64_t sum = 0;
        for (int i = 0; i < x; ++i) sum += A[n-i-1];
        suf[n-x] = sum;
        for (int i = n-x-1; i >= 0; --i) {
            sum += A[i];
            sum -= A[i+x];
            suf[i] = min(suf[i+1], sum);
        }
        sum = 0;
        for (int i = 0; i < x; ++i) sum += A[i];
        int64_t best_left = sum;

        for (int i = x; i + x < n; ++i) {
            res = min(res, best_left + suf[i+1]);
            sum -= A[i-x];
            sum += A[i];
            best_left = min(best_left, sum);
        }
    }
    cout << accumulate(A, A+n, 0LL) - res;
}