Задача №1702. Массивы
Вам дан набор из \(3 \times N\) целых чисел \((X_1, X_2, \dots, X_{3N})\). Составьте три последовательности \((A_1, A_2, \dots, A_N)\), \((B_1, B_2, \dots, B_N)\) и \((C_1, C_2, \dots, C_N)\), такие что:
1) Каждое из чисел принадлежит в точности одной из последовательностей A, B или C
2_ Значение \(S=\sum\limits_{i=1}^N (X_{Ai} - X_{Bi}) \times X_{Ci}\) максимально возможное.
1 \(\le\) \(N\) \(\le\) 10 1 \(\le\) \(T\) \(\le\) 1000
11 \(\le\) \(N\) \(\le\) 15 1 \(\le\) \(T\) \(\le\) 100
16 \(\le\) \(N\) \(\le\) 20 1 \(\le\) \(T\) \(\le\) 10
21 \(\le\) \(N\) \(\le\) 25 1 \(\le\) \(T\) \(\le\) 1
Входной файл содержит \(T\) тестовых блоков с одинаковым значением \(N\). Первая строка входного файла содержит целые числа \(T\) и \(N\). Ограничения на \(T\) и \(N\) приведены в таблице. Каждая из последующих \(T\) строк описывает очередной тестовый блок и содержит 3\(N\) целых чисел — элементов последовательности {\(X\)}. Все значения находятся в пределах от 0 до 1000.
Выходной файл должен состоять из \(T\) строк. В каждую из строк выведите максимально возможное значение \(S\) для соответствующего тестового блока.