Может, ошибка возникает, если инпут из одного символа? Потому что негде там набажить, неправильно посчитанные расстояния между кнопками проверяются претестами
Я, чтобы не рисковать, написал d[k][j] - ответ, если нажали К клавиш, один наш палец на клавише с К-той цифрой, а второй на клавише j. Но должно было пройти и по 3 параметрам, вроде бы, ни с МЛом, ни с ТЛом проблем нету.
В задаче D проходит жадность: сначала мы на каждый корабль должны посадить одного хорошего человека, потом нужно попытаться распределить всех плохих людей так, чтобы ни на один корабль никого досаживать не пришлось. Потом, если есть такая позиция, куда можно посадить плохого, что придется посадить только еще одного хорошего, то тогда помещаем его туда. А после этого постоянно будем сажать плохих на крайний левый корабль. Как-то так :-) Ну и естественно нужно учесть случай, когда есть только один корабль
Ну или можно забить константы с помощью какой-то многомерной динамики - к примеру F(номер корабля, количество уже посаженых хороших, количество хороших в последнем корабле, количество плохих в предпоследнем корабле, количество плохих в последнем корабле) -> максимальное общее число плохих. Есть и более оптимальные ДП, которые не требуют много памяти и забивать константы не надо, но эта проста как пень.
Перебираем, сколько сажаем "плохих" на текущий корабль, вычисляем минимум, сколько надо посадить "хороших" на предыдущий. И ещё минимум для последнего.
И естественные отсечения, что суммарное количество уже посаженных не превышает общего количества.
Ну может быть и надо было. Просто я обычно не люблю писать что-то совсем уж близкое к миллиарду :) и я всё оставшееся время контеста пытался придумать что-то, что работает быстрее :)
в моей терминологии n - число запросов и m - число окон.
Разобъём по координате X все поле на 2^14 полосок, построим по этому делу дерево отрезков. Каждому интервалу соответствует другое дерево отрезков (теперь по Y), включающее все точки-запросы лежащие на полосках соотвутствующих этому интервалу (максимум n штук <= 10^4). каждая точка-запрос попадёт максимум в 14 деревьев, поэтому памяти у нас n * log(n). ах да, в вершине второго дерева отрезков лежат пары (time, window_id). Чтобы узнать цвет ячейки мы вибираем максимум из всех интервалов, которые её содержат O(TreeSize), таким образом чтобы покрасить какую-либо ячеку в нужный цвет нам достаточно присвоить этот цвет любому интервалу содержащему её.
UPD: последнее утверждение верно для деревьев по Y, и для дерева по X, ну и понятно почему оценка O(Log(n)^2) - сначала для дерева по X получаем Log(n) интервалов, и там на каждом дереве запрос будет стоить Log(n)
Там запас топлива не нужен больше 200. Итого 1000 * 200 состояний, 1000 * 1000 * 200 ребер - зашло Дейкстра.
Альтернативно можно сделать 100 * 100 * 200 вершин (для каждой вообще клетки) и только же * 4 ребер - просто ход в сторону или +1 топлива, и тоже пустить Дейкстру.
Странно что Дейкстра зашла. Вроде бы и ребер 2 * 10 ^ 8, и вершин 2 * 10 ^ 5. Если писать сетом, то получаем O(m * log(n)), если как обычно то O(n ^ 2). Видимо, стоило писать сетом, ведь константа невелика(обновляем значения не так часто). Или ты использовал еще какие-то соображения?
Ну и естественно нужно учесть случай, когда есть только один корабль
Что значит "забить константы"?
upd: А, прекальк чтоль.
Можно было простой рекурсивный перебор написать.
Перебираем, сколько сажаем "плохих" на текущий корабль, вычисляем минимум, сколько надо посадить "хороших" на предыдущий. И ещё минимум для последнего.
И естественные отсечения, что суммарное количество уже посаженных не превышает общего количества.
Он вроде даже по времени проходил.
Как решалась Е третьего раунда?
Для каждого запроса ищем максимум за O(n) (перебираем все окна, проверяем координаты и смотрим время его отрисовки поверх остальных).
А как решать за O(m * log2 n)?
в моей терминологии n - число запросов и m - число окон.
Разобъём по координате X все поле на 2^14 полосок, построим по этому делу дерево отрезков. Каждому интервалу соответствует другое дерево отрезков (теперь по Y), включающее все точки-запросы лежащие на полосках соотвутствующих этому интервалу (максимум n штук <= 10^4). каждая точка-запрос попадёт максимум в 14 деревьев, поэтому памяти у нас n * log(n). ах да, в вершине второго дерева отрезков лежат пары (time, window_id). Чтобы узнать цвет ячейки мы вибираем максимум из всех интервалов, которые её содержат O(TreeSize), таким образом чтобы покрасить какую-либо ячеку в нужный цвет нам достаточно присвоить этот цвет любому интервалу содержащему её.
UPD: последнее утверждение верно для деревьев по Y, и для дерева по X, ну и понятно почему оценка O(Log(n)^2) - сначала для дерева по X получаем Log(n) интервалов, и там на каждом дереве запрос будет стоить Log(n)
UPD2: код