All submissions for this problem are available.
You have a board divided into N ×N squares and two robots, R2D2 and C3P O. Each square on the board has a number written on it
R2D2 starts at the top left corner square of the board and C3P O starts at the top right corner square of the board. Your aim is to move the robots so that R2D2 reaches the bottom right corner square and C3P O reaches the bottom left corner square. You have a remote control with two buttons, blue and yellow, that control the robots as follows.
- Whenever you press the blue button, R2D2 moves one square to the right and C3P O moves one square down.
- Whenever you press the yellow button, R2D2 moves one square down and C3P O moves one square left.
The robots are not allowed to move oﬀ the board—if pushing a button would force either one of the robots to move oﬀ the board, the button push has no eﬀect and both robots stay where they are.
For each robot, you compute a score which is the sum of the numbers on the squares that it visits along the path that it follows from its starting position to its ﬁnal position. The combined score of the two robots is the sum of their individual scores. Your aim is to compute the maximum combined score that the two robots can achieve.
For example, suppose you have a 4 × 4 board as follows.
In this example, if R2D2 follows the path marked by ∗ and C3PO follows the path marked by †, as shown below, their combined score is 56.
The ﬁrst line of input is a single integer N, the size of the square board. This is followed by N lines, each containing N space separated integers. For 1 ≤ i ≤ N, the integers on line i+1 of the input describe row i of the board.
A single integer, the maximum combined score that the two robots can achieve. .
- 1 ≤ N ≤ 2500
- -9999≤ score on each square ≤ 9999
Input: 4 6 0 3 -1 7 4 2 4 -3 3 -2 8 13 10 -1 -4 Output: 56
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.