Game on 2d grid
Time Limit: 2.0 s
Memory Limit: 256.0 MB
Description
You are playing a game in which your task is to gain as much point as possible from a 2*N grid. Each of the cell is denoted by a pair of indices \((i,j)\) that means the cell in the intersection of \(i\)-th row and \(j\)-th column and contains an integer \(Ai,j\).
Your character is standing at cell \((1,1)\) and will have to end at cell \((2,N)\). You have three options to move your character:
- move to the right cell, in other words cell \((i,j)\) to cell \((i,j+1)\)
- move to the down cell, in other words cell \((i,j)\) to cell \((i+1,j)\)
- jump any number of consecutive cells to the right that means chose some arbitary number \(x\) and jump from cell \((i,j)\) to cell \((i,j+1+x)\) , this operation will cost \((j+1)+(j+2)+(j+3)+...+(j+x)\) points. In other words if you jump over a cell \((i,j)\) it will cost you \(j\) points.
Every cell \((i,j)\) you visit the value \(Ai,j\) will be added to your score.
What is the maximum score you can achieve from the game.
Note: Your character must visit cell \((1,1)\) and cell \((2,N)\)
Input
First line of input takes an integer \(T\) : number of testcases
First line of each testcase takes an integer \(N\) : number of columns
Second and third line each takes \(N\) integers A\(i,j\) : points of the cell
\(1 \le T \le 1000\)
\(1 \le N \le 2*10^5\)
\(-10^9 \le Ai,j \le 10^9\)
sum of \(N\) over all testcase will not exceed \(2*10^5\)
Output
Output one integer in each of the \(T\) line : the maximum score you can achieve
Sample
Input | Output |
---|---|
|
|
testcase 1:
One of the optimal way is:
visit cell (1,1) score = 1
visit cell (1,2) score = 1+1 = 2
visit cell (1,3) score = 2+2 = 4
visit cell (2,3) score = 4+4 = 8
visit cell (2,4) score = 8+5 = 13
testcase 2:
one of the optimal way is:
visit cell (1,1) score = 1
jump cell (1,2) score = 1-2 = -1
visit cell (1,3) score = -1+2 = 1
visit cell (1,4) score = 1+4 = 5
visit cell (2,4) score = 5+5 = 10
testcase 3:
without jumping over any cell any of the valid path will give the same answer -7
Information
- ID
- 1050
- Difficulty
- 7
- Category
- Greedy Click to Show
- Tags
- (None)
- # Submissions
- 29
- Accepted
- 7
- Accepted Ratio
- 24%
- Uploaded By
Related
In following contests: