import java.util.Scanner;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
public class Conditioners {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
try {
for (; q > 0; q--) {
int n = sc.nextInt(); int k = sc.nextInt();
int[] a = new int[k]; int[] t = new int[k];
int[] dp = new int[n+1];
for (int i = 1; i < n+1; i++) dp[i] = Integer.MAX_VALUE;
for (int i = 0; i < k; i++) a[i] = sc.nextInt();
for (int i = 0; i < k; i++) {
t[i] = sc.nextInt();
for (int j = a[i]; j >= 0; j--) {
if (dp[j] >= t[i] + Math.abs(a[i] - j)) dp[j] = t[i] + Math.abs(a[i] - j);
else break;
}
for (int j = a[i]; j < n+1; j++) {
if (dp[j] >= t[i] + Math.abs(a[i] - j)) dp[j] = t[i] + Math.abs(a[i] - j);
else break;
}
}
for (int i = 1; i < n+1; i++) {
String s = String.valueOf(dp[i]);
bw.write(s + " ", 0, s.length()+1);
}
System.out.println("");
}
bw.close();
} catch (Exception e) {
}
sc.close();
}
}
Я выразил увеличение (защитный слой) по вертикали и горизонтали в зависимости от количества модулей в ряду или колонке, выбираю минимальное из двух. Количество модулей в строке - число, которое я перебираю бинпоиском, остальное выражаю. Оценка бинпоиска - само d. Потом меняю местами a, b (модули повернуты на 90 градусов) и все повторяю.
В случае, когда слева и справа значения равны я сразу выводил f(mid), но один из тестов ломался. Прописал, что нужно идти влево, решение почти прошло (88 баллов), скопировал метод, прописал что нужно вправо, выбрал лучший - результат не изменился.
Использовал бинпоиск, оценивал монотонность, запрашивая значения от x+1 и x-1, x - аргумент. Скорее всего, из-за неточной оценки программа и ломается, поэтому и решил спросить, что делать в таких случаях, когда возможен произвольный отрезок (на тестовом случае были ряды нулей, в другом случае может быть как минимум 3 равных значения).