Олимпиадный тренинг

Задача . E. Максимальная сумма подмассивов


Задача

Темы: *особая задача дп *2100

Заданы два массива целых чисел \(a\) и \(b\) длины \(n\).

Вы можете выполнить следующую операцию любое количество раз (возможно ноль): поменять местами \(a_i\) и \(b_i\).

Пусть \(f(c)\) – наибольшая сумма среди всех непрерывных подотрезков массива \(c\) (включая пустой подотрезок, сумма которого равна \(0\)).

Ваша задача — посчитать максимально возможное значение \(f(a) + f(b)\), используя вышеупомянутую операцию любое количество раз.

Входные данные

Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\)).

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)).

Третья строка содержит \(n\) целых чисел \(b_1, b_2, \dots, b_n\) (\(-10^9 \le b_i \le 10^9\)).

Сумма \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимально возможное значение \(f(a) + f(b)\), используя вышеупомянутую операцию любое количество раз.


Примеры
№Входные данныеВыходные данные
1 3
3
2 -1 3
-4 0 1
6
4 2 -6 1 6 -4
-6 -2 -3 7 -3 2
2
-2 -5
0 -1 
6
21
0

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет