Laser Tanks
Tag(s):

2 Dimensional, Algorithms, Dynamic Programming, Dynamic programming, Medium

Problem
Editorial
Analytics

Several tanks have been arranged in N x N grid with each cell containing exactly one tank. These tanks are laser tanks - they shoot continuous laser beams instead of bullets. Each tank can shoot in two directions - upwards and rightwards, but in only one direction at a time. Tank located in ith row and jth column can shoot in upwards direction with power Vij and in rightwards direction with power Hij. However, if any horizontal laser beam meets vertical laser beam, they creates a big explosion. That's why, you have to assign directions to tanks in such a way that no explosion happens and maximum firepower is achieved. Firepower is defined as total power of all laser beams which have been shot by the tanks.

INPUT:
First line of input will consists of integer N denoting size of the grid. Next N lines will contain N integers, jth integer in the ith line will contain Hij. Similarly, Next N lines will contain N integers denoting matrix Vij

OUTPUT:
Output the maximum total firepower that can be achieved.

CONSTRAINTS:
1 ≤ N ≤ 1000
1 ≤ Vij ≤ 105
1 ≤ Hij ≤ 105

SAMPLE INPUT
2
1 2
1 2
2 2
1 2

SAMPLE OUTPUT
7
Explanation

.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor

Challenge Name

March Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Basic Programming > Implementation
• Data Structures > Advanced Data Structures
• Math > Geometry
• Algorithms > Dynamic Programming
• Math > Number Theory