Це класична задача динамічного програмування на таблиці.
Позначимо через максимальну суму, яку можна набрати на шляху з лівої верхньої клітинки до клітинки . Оскільки в клітинку можна потрапити лише зверху, зліва або по діагоналі зверху-зліва, отримуємо
де максимум береться лише по тих варіантах, які не виходять за межі поля.
База — \mathrm{dp}[1][1] = A[1][1]. Перший рядок і перший стовпець заповнюються окремо: туди можна дійти єдиним способом, тому там просто накопичується префіксна сума.
Відповідь — \mathrm{dp}[N][M]. Якщо це число додатне, Степан виграв, і в першому рядку виводимо winner, інакше — loser. У другому рядку виводимо саму суму.
Важлива деталь: числа в клітинках можуть бути від'ємними, тому ініціалізувати нулями не можна — використовуйте «мінус нескінченність» для недосяжних станів або акуратно обробіть межі. Сума нуль означає програш, бо умова вимагає саме додатну суму.
Складність — , тобто щонайбільше 10^4 операцій.