Все верно.

Да. Прошло чуть больше 1000 людей.

Это почти невозможно проконтролировать.
И в чём смысл таких действий?

Это максимум по претестам.

У вас же все ресурсы для проверки есть: "запуск", куча времени. Потестируйте :)

Не спешите делать выводы, пока не настал вечер, многие просто не хотят решать днем, скорее всего основная масса придет вечером. Хотя вторая квалификация должна быть легче, т.к. 1000+ участников прошли в первой квале и не будут участвовать сегодня.

Есть две регистрации: на весь VK Cup и собственно на квалификационный раунд. Уже, наверное, третий десяток подобных вопросов пошел.

You are in the top 800 in the Qualification Round 1. Congratulations, Round 1 is already waiting for you!

ввод: standard input

вывод: standard output

http://codeforces.net/contest/159

Пока 3800...

Добро пожаловать: http://codeforces.net/contest/159/customtest

прочитайте внимательно условие раз 5 и тогда поймёте почему ответ неверен.

Эти конкурсы, скорее, помогают осознать, что при желании можно многого достичь... Если приложить к этому много усилий.

Your question has been already answered in Russian in the 1st comment :) If someone has passed qual 1, he can't even register for the qual 2 ))

Я разбивал сначала на группы по цветам (использовал хеши). Затем для каждой группы перебирал все группы, в которых количство кубиков меньше или равно количеству данной и вычислял максимальную длину для этих пар. Быстро вычислить длину можно, построив массив, где x[n] — длина первых n кубиков, отсортированных по убыванию. Претесты по крайней мере прошло :)

Я так решал. Допустим C1 — количество кубиков цвета c1, C2 — количество кубиков цвета с2. Если С1<C2, то максимальное высота из цветов c1 и c2 будет получатся если в начале положить самый большой кубик из c2, а потом чередовать c1 и c2, пока не закончятся кубики в c1. Брать кубики надо в порядке убывания их размера. Если C1=C2, то максимальная высота из цветов c1 и c2 — сумма всех кубиков в c1 и c2. Единственное, что т.к. числа большие в задаче — в начале подсчитать возможные высоты кубиков из одного цвета для каждого цвета для первых i(1<=i<=Cn) кубиков и отсортировать кубики в порядке убывания. Не забываем сохранять ссылки на оригинальные данные, т.к. выводить надо в том порядке, в котором дано.

Я написал тупое ДП.

Для каждого веса отсортируем кубики по убыванию весов. Затем посчитаем максимальный размер башни, который мы получим, если сложим i кубиков данного цвета.

А затем идем по количеству кубиков в половине башни и смотрим, какой максимальный размер мы можем получить. Для этого используем ДП, посчитанное в предыдущем пункте.

Не знаю, пройдет ли мое решение, но вроде должно.

Сначала группируем кубики по цвету, потом каждую группу сортируем по убыванию размера. Затем просто перебираем пары цветов, и ищем максимальную высоту.

Для башни мы всегда берем все кубики того цвета, кубиков которого меньше, и столько-же, или на единицу больше(если есть) кубиков другого цвета.

Чтобы быстро посчитать суммарную высоту — сохраним в массивах частичные суммы для каждого цвета.

E довольно просто решается. Сгруппируем все кубики по цветам, для каждого цвета посортируем кубики по размеру по убыванию. Сами группы посортируем по убыванию размера групп. Заведём глобальный массив MaxSize[] где i-тый элемент это максимальный размер группы (изначально установим все элементы в минус бесконечность. Теперь пройдемся по всем группам по порядку. Пусть мы дошли до группы i. выполним два действия для нее
1) Идём по массиву кубиков в группе и нарасчиваем сумму размеров кубиков в префиксе curSum, пусть сейчас в префиксе j элементов,

res = max(res, curSum + MaxSize[j - 1]);
res = max(res, curSum + MaxSize[j]);
res = max(res, curSum + MaxSize[j + 1]);

2) снова пройдемся по массиву кубиков считая сумму на префиксе и обновляя значения в MaxSize, MaxSize[j] = max(MaxSize[j], curSum) Вместе с обновлением ответа можно запоминать номера групп для вывода в конце всех использованных кубиков.

D я решал так: Динамикой для каждой подстроки узнаем, является ли она палиндромом (сохраним это в матрице)

Теперь нужно для каждого палиндрома узнать, сколько палиндромов начинаются позже, чем он кончается, и эти количества просуммировать — это и будет ответ.

Обойдём всю матрицу. Для каждой единичке в матрице нужно к ответу добавить количество единичек строго ниже неё. Это легко сделать, проходя по строкам снизу вверх, на ходу увеличивая количество единичек.

Тут близко к динамическому программированию. x[n] — количество полиндромов левее n (включая), y[n] — правее. Тогда ответом будет Sum((x[i] — x[i — 1]) * y[i + 1]).

За O(N^2) я нашел все палиндромы. Пусть l[i] — количество палиндромов, начинающихся с символа i, а r[i] — количество палиндромов, заканчивающихся символом i.

Тогда для каждого i пройдем по всем j, лежащим правее, к ответу каждый раз прибавляем r[i] * l[j].

Аналогичное решение

Я не заметил, что размер строки до 2000, поэтому моё решение имеет сложность N Log N и слишком длинное и запутанное чтобы поместиться в этом комментарии.

Решение в лоб за N^3 тоже заходило. :D 1317753

Started already :)

ага, настораживает. моё пока не протестило

Если кто знает, скажите, на чем она падает.

Да, можно посчитать включения всех символов в исходной строке и продублировать на все отрезки (завести массив), а потом в процессе поиска отрезка, в котором нужно исключить символ, проходить по этому массиву, а не по всей строке.

Конечно, упрощает.

Храним K строк, для каждой строки храним колличество каждого символа в ней. Теперь мы можем удалять и искать символ за O(K+Base_len).

Да, это будет засчитано как обычный рейтинговый раунд.

Нормально, ТЛ ведь 3 секунды. Вот был бы 2 секунды, как обычно, не прошло бы это решение.