Жауабы: Максимальная сумма разностей
Дәл два значения зависят от данных файлов A и B, которые не представлены во вложениях.
У этого задания официального ключа нет, поэтому ответ получен в разборе және кілтпен салыстырылмаған. Нәтижені жаттамас бұрын, өтіңіз выкладки — там видно, откуда взялось каждое число.
Бланкке: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S_i$, $S_j$, $S_k$ три элемента последовательности $S$, где $i < j < k$. Определите в последовательности $S$ три таких числа $S_i$, $S_j$, $S_k$, что $S_i < S_j$, $S_k < S_j$, и значение выражения $(S_j - S_i) + (S_j - S_k)$ максимально. Гарантируется, что в последовательности есть три числа, удовлетворяющие условию задачи.
Даны два входных файла — файл A и файл B. В первой строке каждого файла содержится число $N$ ($5 \leq N \leq 10\,000\,000$). Каждая из следующих $N$ строк содержит одно целое число, значение которого по модулю не превышает 1000. Используйте данные из прилагаемых файлов.
Где здесь ошибаются
Перебирать все тройки индексов, что имеет кубическую сложность.
Выбирать максимальные, а не минимальные элементы слева и справа.
Нарушать порядок индексов $i<j<k$.
Использовать первый или последний элемент как средний, хотя по обе стороны от $j$ должны существовать элементы.