Вот краткий разбор тех задач, которые я прочитал на контесте:

Думаю, что здесь ничего не надо разбирать, а просто аккуратно написать то, что от Вас требуют

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

Т. к. НОД(A, B, C) = НОД(НОД(A, B), C), то можно каждую строку матрицы разбить на sqrt(N) блоков и в каждом предпосчитать НОД. Теперь будем отвечать на запросы, проходясь по строкам матрицы честно, а столбцы обрабатывать группами.

A - массив заданных чисел

Посчитаем две вспомогательные величины.

SUM1_i - сумма чисел с A₁ по A_i

SUM2_i - сумма чисел A_i, A_i+2, A_i+4 и т.д.

Максимум в первой строке всегда будет A₁, а максимум второй строки мы переберем. Понятно, что максимум второй строки можно разместить под A₁ и ответ от это не ухудшится. Пусть мы сейчас смотрим на число A_i, тогда вверх точно должно пойти числа с A₂ по A_i-1, т. к. мы планируем сделать A_i максимумом во второй строке. Значит мы "под" эти числа можем поставить числа с A_i+1 по A_{2 * (i - 1)}. Ответ от этого не ухудшится. Теперь надо оставшиеся числа разбить на пары. Максимальное число в паре поставим вверх, а минимальное - "под" максимальное. Тогда ответ для такой конфигурации будет (A₁ + A_i) * (SUM1_{i - 1} - SUM1₁ + SUM2_{2 * i - 1} + A₁). Из всех конфигураций нужно взять минимум.

http://pastebin.com/UtsWkV1F 

SUM - массив сумм префиксов.

Будем решать задачу динамикой. D_{i, j} - максимальная сумма, которую мы можем получить, сделав не более i зачеркиваний и используя первые j чисел.

D_{i, j} = max(D_{i, j - 1}, D_{i - 1, j - k} + SUM_j - SUM_{j - k})