Educational Codeforces Round 28 |
---|
Закончено |
Задан массив из n целых чисел. Пусть sum(l, r) — сумма чисел на индексах с l по r не включительно (l-й элемент учитывается, r-й элемент не учитывается). Индексы l и r таковы, что 0 ≤ l ≤ r ≤ n. Индексы в массиве нумеруются с 0.
Например, если массив a = [ - 5, 3, 9, 4], то sum(0, 1) = - 5, sum(0, 2) = - 2, sum(1, 4) = 16, и sum(i, i) = 0 для всех i от 0 до 4.
Выберите три индекса delim0, delim1, delim2 (0 ≤ delim0 ≤ delim1 ≤ delim2 ≤ n) и поделите массив таким образом, чтобы величина res = sum(0, delim0) - sum(delim0, delim1) + sum(delim1, delim2) - sum(delim2, n) была максимальна.
Обратите внимание, что некоторые значения sum(l, r) могут соответствовать пустым отрезкам (если l = r для соответствующего отрезка).
В первой строке записано одно целое число n (1 ≤ n ≤ 5000).
Во второй строке записаны n целых чисел a0, a1, ..., an - 1 ( - 109 ≤ ai ≤ 109).
Выведите три таких индекса, что величина res — максимальна. Если существует несколько ответов, выведите любой из них.
3
-1 2 3
0 1 3
4
0 0 -1 0
0 0 0
1
10000
1 1 1
Название |
---|