Задача №115195. Три массива
Вам даны три массива \(D\), \(L\) и \(R\) длины \(n\), нумерация элементов которых ведется с \(1\), а также числа \(a_{0}\) и \(b_{0}\). Вы строите два массива \(A\) и \(B\) длины \(n+1\) по следующим правилам:
- \(A_{0} = a_{0}\), \(B_{0} = b_{0}\)
-
Для всех \(i\) от \(1\) до \(n\) вы делаете следующие действия:
- Задать элементы, как \(A_{i} = A_{i - 1} + D_{i}\) и \(B_{i} = B_{i - 1} + D_{i}\).
-
Выбрать ровно
одну
из операций ниже и применить её:
- \(A_{i} = \min(A_{i}, L_{i})\)
- \(B_{i} = \min(B_{i}, R_{i})\)
Вы хотите построить массивы \(A\) и \(B\) так, чтобы максимизировать значение \(A_{n} + B_{n}\). Найдите максимальное значение \(A_{n} + B_{n}\), которое можно получить, выполняя описанные выше действия.
В первой строке дано одно целое число \(n\) (\(1 \le n \le 100\,000\)) — длина массивов \(D\), \(L\) и \(R\).
Во второй строке даны \(n\) целых чисел \(D_{1},\ D_{2},\ \ldots,\ D_{n}\) (\(0 \le D_{i} \le 10^{9}\)) — массив \(D\).
В третьей строке даны \(n\) целых чисел \(L_{1},\ L_{2},\ \ldots,\ L_{n}\) (\(0 \le L_{i} \le 10^{9}\)) — массив \(L\).
В четвертой строке даны \(n\) целых чисел \(R_{1},\ R_{2},\ \ldots,\ R_{n}\) (\(0 \le R_{i} \le 10^{9}\)) — массив \(R\).
В пятой строке даны два целых числа \(a_{0}\) и \(b_{0}\) (\(0 \le a_{0}, b_{0} \le 10^{9}\)).
Выведите единственное число — максимально возможное значение \(A_{n} + B_{n}\) среди всех возможных вариантов построить массивы \(A\) и \(B\).
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(D_i\) | Необх. группы | Комментарий |
| \(0\) | \(0\) | – | – | – | Тесты из условия. |
| \(1\) | \(13\) | \(n \le 15\) | – | \(0\) | |
| \(2\) | \(18\) | \(n \le 300\) | – | \(0\), \(1\) | |
| \(3\) | \(14\) | \(n \le 5000\) | \(D_{i} = 0\) | – | |
| \(4\) | \(16\) | \(n \le 5000\) | – | \(0\)–\(3\) | |
| \(5\) | \(19\) | – | \(D_{i} = 0\) | \(3\) | |
| \(6\) | \(20\) | – | – | \(0\)–\(5\) | Offline-проверка. |
В первом наборе входных данных следующая последовательность действий приводит к максимальному ответу:
- \(A_{0} = 4\), \(B_{0} = 8\).
- \(A_{1} = A_{0} + D_{1} = 4 + 4 = 8\), \(B_{1} = B_{0} + D_{1} = 8 + 4 = 12\).
- Минимум применяется для \(A_{1} = \min(A_{1}, L_{1}) = \min(10, 8) = 8\), значение \(B_{1} = 12\) остается прежним.
- \(A_{2} = A_{1} + D_{2} = 8 + 0 = 8\), \(B_{2} = B_{1} + D_{2} = 12 + 0 = 12\).
- Минимум применяется для \(A_{2} = \min(A_{2}, L_{2}) = \min(5, 8) = 5\), значение \(B_{2} = 12\) остается прежним.
- \(A_{3} = A_{2} + D_{3} = 12\), \(B_{3} = B_{2} + D_{3} = 19\).
- Минимум применяется для \(A_{3} = \min(A_{3}, L_{3}) = 3\), значение \(B_{3} = 19\) остается прежним.
- \(A_{4} = A_{4} + D_{3} = 3\), \(B_{4} = B_{3} + D_{4} = 19\).
- Минимум применяется для \(A_{4} = \min(A_{4}, L_{4}) = 3\), значение \(B_{4} = 19\) остается прежним.
- \(A_{5} = A_{5} + D_{4} = 11\), \(B_{5} = B_{4} + D_{5} = 27\).
- Значение \(A_{5} = 11\) остается прежним, \(B_{5} = \min(B_{5}, R_{5}) = \min(27, 23) = 23\).
- \(A_{5} + B_{5} = 11 + 23 = 34\).
Можно показать, что это является максимальным значением.
5 4 0 7 0 8 10 5 3 7 7 8 5 9 2 23 4 8
34