Да, красивое решение

Не совсем уверен, но, по-моему, можно сделать за 3ю степень полностью забив на вторую фирму. Состояние (качество фирмы номер 1, какой фирме принадлежит текущая вершина). Все остальное тоже, только пересчитываем за квадрат. Так мы посчитаем матожидание денег, которое заплатит первая фирма. Умножив на два эту величину получим ответ.

У меня получалось либо решить задачу для формулировки, когда можно делать циклы длины 2, либо только проверить, есть ли решение для исходной задачи (когда нельзя делать циклов длины 2). Объединить так и не вышло.

Сделаем граф двудольным. S — исток, T — сток, v — вершина, v_1 — копия вершины горизонтальная, v_2 — копия вершины вертикальная.

Будем искать сейчас mincost-maxflow добавим ребра пропускных способностей 2 и стоимости 0 из S->v, v->T. Дальше, добавим два ребра из v -> v_i пропускных способностей 1 и стоимостей 0 и field[i][j] == 'C'. дальше соеденим вертикальные копии с вертикальными и горизонтальные с горизонтальными ребрами стоимости 0 и пропускных способностей 1. дальше пустим поток понятно какой велечины проверим, что он достаточно большой и выведем стоимость. Кажется баги нет семплы оно проходило до глюков с ареной у моего компа.

Решение прошло в дорешке тупой Форд Беллман с очередью работает максимум 100ms.