## EZtra 1

This article will not directly provide the answer code, but will give you a few hints and explain which ideas should be inappropriate.

## Description

[Problem link](https://oj.cerana.tech/contest/6/problem/4)

Find the largest cross sum in the matrix. The length of the cross is **E**. What is special is that the cross will stop extending once it hits the wall (M[i][j] = -100001).

## Approach 1: Brute force search (TLE)
If you were just running through each point and simulating each explosion, consider the following example:

3 3 3 3 3 3 3 3 ... 3 3 3 3 3 3 3 3 // no walls

When M is large, your program code will need to look at the entire matrix at each point, and obviously many of these operations are repeated and redundant.

In fact, if each value is calculated N times (N represents the size of this matrix), then overall, your code needs to be calculated N^2 times.

## Hint 1: Prefix Sum
Let’s think about the problem simply. Assume that the problem has no walls, and the matrix always has only 1 row. How can we quickly get the value of a point when it explodes?

Consider the following example:

E = 1
M = 5 2 3 2 4 6

So what happens if we accumulate each value of the matrix from left to right?

we will get
5 5+2 5+2+3 5+2+3+2 5+2+3+2+4 5+2+3+2+4+6
5 7 10 12 16 22

So how are these accumulated values converted into answers?

It is not difficult to find out by observation that the score of detonation for each bomb can be obtained by subtracting the leftmost end from the rightmost end of the explosion range.

M = 5 2 3 2 4 6
PreM = 5 7 10 12 16 22
Detonate at (0,0) = 7 - 0 = 7
Detonate at (0,1) = 10 - 0 = 10
Detonate at (0,2) = 12 - 5 = 7
Detonate at (0,3) = 16 - 7 = 9
Detonate at (0,4) = 22 - 10 = 12
Detonate at (0,5) = 22 - 12 = 10

When E = 1, we can see that the correct answer should be (0, 4) 12

## To be continued...