Гра#501

Гра (Розбір)

Автор: Костянтин Денисов

Роздробник: Павло Цікалишин

Розбір підготовано: Костянтин Денисов

Очевидно, що на відрізку $[l, r]$ [l,r] треба ставити якнайбільші числа, тобто $a_{i} = m$ a_i=m для всіх $l \leq i \leq r$ l \le i \le r. Тоді цей відрізок має найбільший потенціал, і далі наша задача — зробити так, щоб жоден інший підвідрізок не міг з ним зрівнятися за сумою, та ще й серед усіх таких масивів максимізувати суму невід'ємних елементів.

Окремий випадок $l = r$ l=r. Тут максимальна сума має бути рівно $m$ і досягатися лише на позиції $l$ . Тому поза $l$ не можна ставити $m$ , інакше одиночний підвідрізок з цієї позиції теж матиме суму $m$ . Отже поза $l$ найкраще ставити $m - 1$ m-1. Але треба ще зіпсувати всі підвідрізки, які включають $l$ і ще щось: для цього достатньо розставити $- m$ на кожній другій позиції, починаючи від сусідів $l - 1$ l-1 та $l + 1$ l+1. Тоді будь-яке розширення відрізка за межі $[l, l]$ [l,l] неминуче підхопить хоча б один $- m$ , і сума стане строго меншою за $m$ .

Випадок $l < r$ l<r.

Поза відрізком $[l, r]$ [l, r] оптимальна конфігурація має максимально багато $m$ , але такі $m$ доводиться ставити через один, чергуючи з $- m$ ; інакше з'являється занадто великий підвідрізок поза $[l, r]$ [l,r] або підвідрізок, що "приклеюється" до $[l, r]$ [l,r].

Тому для префікса довжини $s = l - 1$ s=l-1 оптимально ставити (зліва направо):

якщо $s$ парна, то $m, - m, m, - m, \dots, m, - m, m - 1, - m$ m,\,-m,\,m,\,-m,\,\dots,\,m,\,-m,\,m-1,\,-m; доводиться ставити одну $m - 1$ m-1, щоб сума елементів була від'ємна, бо інакше буде декілька елементів з однаковою максимальною сумою.
якщо $s$ непарна, то $m, - m, m, - m, \dots, m, - m, - m$ m,\,-m,\,m,\,-m,\,\dots,\,m,\,-m,\,-m.

Для суфікса довжини $t = n - r$ t=n-r робимо аналогічну (дзеркальну) побудову за парністю $t$ .

У будь-якому допустимому масиві поза $[l, r]$ [l,r] не можна ставити багато великих додатних підряд: кожен додатний $m$ змушений мати поруч достатню "компенсацію" $- m$ , інакше з'являється підвідрізок з занадто великою сумою, який конкурує з $[l, r]$ [l,r]. Отже $m$ можна ставити не частіше, ніж через один, тобто шаблон $m, - m, m, - m, \dots$ m,-m,m,-m,\dots дає максимальну кількість $m$ . У парному випадку рівно один раз доводиться замінити $m$ на $m - 1$ m-1, щоб уникнути рівності максимумів.

Складність. Побудова займає $O (n)$ часу і $O (1)$ додаткової пам'яті (окрім виводу).