1677: Мінімальна різниця між сумами


Submit solution

Points: 32
Time limit: 2.0s
Python 3.0s
Memory limit: 64M
Python 250M

Author:
Problem type

Задається послідовність цілих чисел \(A\) довжиною \(N\).

Розіб'ємо дану послідовність на чотири суміжних непорожніх підпослівностей. Позначимо їх суми \(P,Q,R,S\).

Ваша задача розбити послідовність так, щоб абсолютна різниця між максимальною та мінімальною сумами з \(P,Q,R,S\) була мінімальна. Знайдіть цю різницю.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\) \((4 \le N \le 2 \cdot 10^5)\)

Наступний рядок містить цілі числа \(A_i\) \((1 \le A_i \le 10^9)\), які розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану мінімальну абсолютну різницю між максимальною та мінімальною сумами серед \(P,Q,R,S\)

Приклад вхідних даних

5
3 2 4 1 2

Приклад вихідних даних

2

Comments

There are no comments at the moment.