Codeforces Round 775 (Div. 1, по задачам Открытой олимпиады школьников по программированию) |
---|
Закончено |
Дима находится на шоу от бизнесмена Петра. В этом шоу Диме предстоит пройтись по дорожке, которая является прямоугольником $$$3 \times n$$$, где строки пронумерованы от $$$1$$$ до $$$3$$$ сверху вниз, а столбцы от $$$1$$$ до $$$n$$$ слева направо.
На клетке на пересечении строки $$$i$$$ и столбца $$$j$$$ написано число $$$a_{i,j}$$$. Изначально у Димы есть баланс, равный нулю, и когда Дима наступает на клетку в $$$i$$$-й строке и $$$j$$$-м столбце, его баланс меняется на $$$a_{i,j}$$$ рублей. Баланс может становиться отрицательным.
Дима может заходить на любые клетки первой и третьей строки, но изначально клетки второй строки для него недоступны. Однако есть $$$q$$$ предложений от бизнесмена Петра, которые могут сделать их доступными: $$$i$$$-е предложение позволяет разблокировать все клетки второй строки на отрезке с $$$l_i$$$ по $$$r_i$$$, заплатив за это $$$k_i$$$ рублей. Дима может воспользоваться любым количеством таких предложений, а также разблокировать одну и ту же клетку несколько раз.
Дима изначально стоит на клетке в клетке $$$(1, 1)$$$ и хочет попасть в клетку $$$(3, n)$$$. За один ход Дима может подвинуться на 1 вправо или вниз, то есть увеличить на 1 номер строки или столбца. Таким образом, всего в процессе пути Дима сделает $$$n + 1$$$ ход, из которых ровно $$$n - 1$$$ будет по горизонтали и $$$2$$$ по вертикали.
Выигрыш Димы будет равен финальному балансу после совершения всех ходов, то есть сумме чисел на всех посещённых клетках за вычетом стоимости всех использованных предложений. Ваша задача — определить максимальный возможный выигрыш Димы.
В первой строке даны два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 500\,000$$$) — длина прямоугольника и число возможных отрезков для разблокировки.
В следующих трёх строках описываются числа в прямоугольнике, в $$$i$$$-й строке даны $$$n$$$ целых чисел $$$a_{i1}$$$, $$$a_{i2}$$$, ..., $$$a_{in}$$$ ($$$-10^9 \le a_{ij} \le 10^9)$$$ — числа в $$$i$$$-й строке прямоугольника.
В следующих $$$q$$$ строках описываются доступные предложения для разблокировки отрезков, в $$$i$$$-й из них даны три целых числа $$$l_i$$$, $$$r_i$$$ и $$$k_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$1\leq k_i\leq 10^9$$$) — границы разблокируемого отрезка и стоимость предложения.
Выведите одно число — максимальный возможный выигрыш Димы.
4 3 1 0 2 -1 -3 1 9 2 3 2 4 1 1 2 5 2 3 4 1 4 14
13
5 4 -20 -10 -11 -10 1 1 3 3 6 3 14 -20 3 6 2 1 5 13 1 2 2 3 5 3 2 3 1
-4
В первом примере оптимально воспользоваться вторым предложением Петра за $$$4$$$ рубля и пройти по клеткам $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$, заработав $$$1 + 0 + 2 + 9 + 4 + 1 - 4 = 13$$$ рублей.
Во втором примере оптимально воспользоваться вторым и третьим предложением Петра за $$$2$$$ и $$$3$$$ рубля соответственно, и пройти по клеткам $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, заработав $$$-20 + 1 + 3 + 3 + 6 + 6 + 2 - 2 - 3= -4$$$ рубля.
Название |
---|