1695: Матрична гра

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 40
Time limit: 3.0s
Memory limit: 500M

Author:
Problem type

Ви граєте в матричну гру з такими налаштуваннями та правилами:

  • Вам дається матриця \(A\) розмірності \(n \times m\). Кожна клітинка матриці містить цілі числа. Коли гравець проходить через клітинку, його рахунок збільшується на число, записане в цій клітинці, і число в клітинці стає рівним 0. Якщо число у клітинці від'ємне, то кількість балів зменшиться на це число.

  • Гравець починає гру з будь-якої клітинки в першому ряду і може рухатися вліво, вправо або вниз.

  • Гра закінчується, коли гравець досягає останнього ряду і зупиняється.

Який максимальний бал зможе отримати гравець.

Формат вхідних даних

Перший рядок вхідного потоку містить цілі числа \(n,m\) (\(1 \le n \times m \le 4 \times 10^6\))

Наступні \(n\) рядків містять по \(m\) цілих чисел - елементи \(A_{ij}\) (\(-250 \le A_{ij} \le 250\)) матриці \(A\). Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести максимальний бал гравця.

Приклад вхідних даних

4 5
1 2 3 -1 -2
-5 -8 -1 2 -150
1 2 3 -250 100
1 1 1 1 20

Приклад вихідних даних

37

Приклад вхідних даних

10 1
1
2
3
4
5
6
7
8
9
10

Приклад вихідних даних

55

Коментарі

Ще немає коментарів.