Не знаю как ты, а я пострадал.. Минут 40 думал тупо над идеей условия

ДП на ациклическом графе: dp[i] равно 1, если, начиная из i-ой вершины, мы сможем гарантировать, что сигнал не дойдет до сердца, и 0 иначе.
Как считать: идем по вершинам в обратном порядке, dp[n] = 0, для остальных i считаем с, равное количеству ребер, идущих в вершины j, такие, что dp[j] = 0. Понятно, что все эти ребра будут идти в уже рассмотренные вершины с посчитанным dp[j]. Итак, если c ≤ k, то, очевидно, dp[i] = 1 (т.к. мы сможем блокировать все ребра в "плохие" вершины с dp[j] = 0), иначе dp[i] = 0.
Если dp[1] = 0, ответ NO, иначе на каждом шаге блокируем ребра в "плохие" вершины и, тем самым, выигрываем жюри.

Решается задача H очень просто:) (мой код)

Из условия видно, что данный нам граф ациклический, так как написано, что в нем такие ребра:

a -> b, где a меньше b.

Будет считать такую динамику на этом ациклическом графе:

f[v] — всегда ли может ли сигнал дойти из v-ой вершины в n-ую. видно, что f[n] = true;

Для остальных вершин v считается так:

считаем кол-во d — кол-во вершин смежных вершин to, что f[to]=true.

если d>k то f[v]=true;

Посчитав динамику мы можем видеть, что если f[1]==true, то нужно вывести "NO";

А если f[1]=false, то мы сможем оптимально решить задачу так:

Перекрываем все ребра v->to, где f[to]=true, а v — вершина в которой находится сигнал.

F — вполне стандартная задача. Можно почитать e-maxx

На каждом шагу пытаемся найти наибольшее кол-во задач которую сможет решить вся команда. Строим двудольный граф на членах команды и нерешенных задачах. Запускаем поиск максимального паросочетания.

Повторяем вышеописанные операции раз.

Код

Как ни странно, решаем потоками)

Построим граф такой, что 0 — исток, 1..m — задачи, (m + 1)...(m + n) — участники, (m + n + 1) — сток. Из истока ребра пропускной способности 1 к каждой задаче, от задач — ребра пропускной способности 1 к участникам, которые умеют её решать. Из участников ребра в исток пропускной способности размера X. Будем перебирать X от 1 до максимального количества задач, которое может решить один человек за контест. При увеличении X пускаем поток по сети, которая получилась из предыдущих X, пока пускается (то есть мы не зануляем поток, а используем старые значения)

А, ну и ответ обновляем: общее количество задач — это поток, который течет из истока в сток, а штрафное время считается, как сумма ((1 + f[i][t]) * f[i][t] / 2) * L, (t — сток) для всех i от (m + 1) до (m + n), ну то есть всех участников

Нестандартная задача на подумать. Чем плохо?

Интересно, кто нибудь решал эту задачу, без поиска артиклей и местоимений.

По моему очень интересная задача. Ее можно даже эвристической назвать, хотя может кто поспорит. Мы перебрали не одну интересную идею, прежде чем решили ее. Мне задача понравилась.

Выглядит как HLD чистой воды.

Где-то тут была задача, как уложить дерево на дерево отрезков. Посортируем вершины в порядке времени входа и заметим, что поддерево является подотрезком.

UPD 343D

А время неудачных посылок участников-призраков выставляется рандомно? Простите, если глупый вопрос, я просто только сейчас увидел, что оно не соответствует, мне стало интересно

Большое спасибо за указание на ошибку.

От лица жюри олимпиады приношу извинения и уверяю Вас, что такое больше не повторится.

Все авторские решения работают 1200-1300 мс. Конечно, если такое решения как ваше не предполагалось, то надо опустить TL.

Почему невозможно? Авторское решение работает совсем быстро и написано на Java.