images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 21:36:07

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2472. Разбиение последовательности

Ограничения: время – 350ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Дана последовательность из `N` целых положительных чисел `A_1,\ A_2,\ …,\ A_N`. Найдите способ разбиения последовательности на две части так, чтобы произведение суммы квадратов элементов первой части последовательности на сумму элементов второй части последовательности было максимальным, то есть нужно найти максимум значения выражения
`(A_1^2\ +\ …\ +\ A_k^2)*(A_{k+1}\ +\ …\ +\ A_N)`.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^6`). Далее следует `N` строк, содержащих по одному целому числу – элементы последовательности `A_i` (`1\ ≤\ A_i\ ≤\ 100`).
Вывести одно целое число – максимум указанного выражения.

Пример ввода 1

5
1
2
4
3
5

Пример вывода 1

168

Пример ввода 2

2
1
1

Пример вывода 2

1

Пример ввода 3

10
5
8
10
9
1
4
12
6
13
3

Пример вывода 3

10530
Система оценки и описание подзадач
Подзадача 1 (40 баллов)
`1\ ≤\ N\ ≤\ 100`
В этой подзадаче 10 тестов, каждый тест оценивается в 4 балла. Баллы за каждый тест начисляются независимо.
Подзадача 2 (40 баллов)
Необходимые подзадачи: 1.
`100\ <\ N\ ≤\ 10^5`
В этой подзадаче 8 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (20 баллов)
Необходимые подзадачи: 1,2.
`10^5\ <\ N\ ≤\ 10^6`
В этой подзадаче 4 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
loading